排序 + 动态规划

两个性质: ①得分最高 ② 年龄大的，分数要高。
这提示我们按照分数，或者年龄，对列表排序。先固定一个性质，才考虑另外的性质。

按照分数和年龄排序都可以。这里按照年龄，从大到小排序。年龄大的，自然在前；年龄相同，分数大的在前。在排序后的数组里，找到最大下降子序列和，满足一个条件 —— 越靠前，分数越大。即为所求。

状态定义： f[i]f[i]f[i] 表示所有以 p[i]p[i]p[i] 结尾的最大下降子序列和。
状态转移方程： f[i]=max(f[j])+p[i],j∈[0,i)f[i] = max(f[j]) +p[i], \ j \isin [0,i)f[i]=max(f[j])+p[i], j∈[0,i)

最后，答案序列不一定以数组末尾结尾，可能在任何位置结尾，需要维护最大的 f[i]f[i]f[i] ，即为答案。

class Solution {
public:static bool cmp(pair x, pair y) {return (x > y);}int bestTeamScore(vector& scores, vector& ages) {int n = scores.size();vector> p(n);for (int i = 0; i < n; i ++) p[i] = {ages[i], scores[i]};sort(p.begin(), p.end(), cmp);vector f(n);int ans = 0;for (int i = 0; i < n ; i ++) {for (int j = i - 1; j >= 0; j --) {if (p[j].second >= p[i].second) {f[i] = max(f[i], f[j]);}}f[i] += p[i].second;ans = max (ans, f[i]);}return ans;}
};

1. 时间复杂度 : O(n2)O(n ^ 2)O(n2) ， nnn 是球员的数目，一共 nnn 状态，平均每个状态转移 nnn 次，时间复杂度 O(n2)O(n^2)O(n2)。
2. 空间复杂度 : O(n)O(n)O(n) ，状态数组和分数-年龄数组的空间复杂度 O(n)O(n)O(n) 。

AC

致语

• 理解思路很重要
• 读者有问题请留言，清墨看到就会回复的。