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