1626. Best Team With No Conflicts
每個球員有分數及年齡，要挑出一支球隊
其中年齡比較大的隊員的分數不能比較小
問總分最高多少
有點像權重版的 longest nondecreasing subsequence
不過寫一寫覺得比想像中麻煩，不太像是 Medium
寫完才發現 n <= 1000 所以其實 O(n^2) 就會過了
首先照年齡排好序後，對於第 i 個球員
在他之前都是年齡比他小的
所以要在那些分數比他小的球員裡選
也就是
DP[i] = max_j (DP[j] + scores[i]) where scores[j] <= scores[i]
到這裡 O(n^2) 的演算法已經可以很容易寫出來了
不過我們可以維護一個 ordered_map 從 score 對應到能得到的總分
並且保持若 a < b 則 map[a] < map[b]
這可以藉由每次插入時都移除那些不符合的人來維護
這樣對於 scores[i] 而言我們只要花 logn 找到在 map 裡
比他小的最大 key 就可以了
因為一個球員最多插入和移除一次
所以最後的複雜度還是 O(nlogn)
class Solution {
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n = scores.size();
using T = pair<int, int>;
vector<T> V(n);
for (int i = 0; i < n; i++)
V[i] = { ages[i], scores[i] };
sort(V.begin(), V.end());
map<int, int> M{{0, 0}}; // score -> total
for (auto [_, sc]: V) {
auto it = M.upper_bound(sc);
it