题目描述

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和。

然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。

给定两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数。

样例

输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5]
输出：34
解释：你可以选中所有球员。

输入：scores = [4,5,6,5], ages = [2,1,2,1]
输出：16
解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。

输入：scores = [1,2,3,5], ages = [8,9,10,1]
输出：6
解释：最佳的选择是前 3 名球员。

限制

• 1 <= scores.length, ages.length <= 1000
• scores.length == ages.length
• 1 <= scores[i] <= 10^6
• 1 <= ages[i] <= 1000

算法1

(排序，动态规划) $O(n^2)$

1. 将所有人按照分数为第一关键字，年龄为第二关键字从小到大排序。（反之亦可）
2. 此时，问题可以转换为，求当前数组的权值最大的不降子序列。
3. 设状态 $f(i)$ 表示以第 $i$ 个为结尾时，所能得到的最大得分。
4. 初始时，$f(i) = scores(i)$。
5. 转移时，对于 $f(i)$，枚举 $j < i$，如果 $ages(j) \le ages(i)$，则转移 $f(i) = \max(f(i), f(j) + scores(i))$。
6. 最终答案为 $\max(f(i))$。

时间复杂度

• 排序需要 $O(n \log n)$ 的时间。
• 动态规划状态数为 $O(n)$，转移需要 $O(n)$ 的时间。
• 故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储排序后的数组以及动态规划的状态。

C++ 代码

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        const int n = scores.size();
        vector<int> rank(n);
        for (int i = 0; i < n; i++)
            rank[i] = i;

        sort(rank.begin(), rank.end(), [&](int x, int y){
            if (scores[x] != scores[y])
                return scores[x] < scores[y];
            return ages[x] < ages[y];
        });

        vector<int> f(n);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            f[i] = scores[rank[i]];
            for (int j = 0; j < i; j++)
                if (ages[rank[j]] <= ages[rank[i]])
                    f[i] = max(f[i], f[j] + scores[rank[i]]);

            if (ans < f[i])
                ans = f[i];
        }

        return ans;
    }
};

算法2

(二维偏序，树状数组) $O(n \log (n + m))$

1. 典型的二维偏序问题，先从小到大双关键字排序。
2. 第一维已经通过排序解决，第二维可以使用优化过的动态规划，即树状数组解决。
3. 由于第二维的范围为 [1, 1000]，所以可以不必离散化。
4. 树状数组 bits(x) 记录 [1, x] 中的得分最大值。
5. 遍历排序后的数组时，首先查询位置小于等于 ages(i) 的最大值 tot，然后用 tot + scores(i) 去更新位置 ages(i)。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 设树状数组的最大范围为 $m$，求解过程的时间复杂度为 $O(n \log m)$。
• 故总时间复杂度为 $O(n \log (n + m))$。

空间复杂度

• 需要 $O(n + m)$ 的额外空间存储排序后的数组和树状数组。

C++ 代码

#define max(x, y) ((x) > (y) ? (x) : (y))

class Solution {
private:
    int m;
    vector<int> bits;

    int query(int x) {
        int res = 0;
        for (; x; x -= x & -x)
            res = max(res, bits[x]);
        return res;
    }

    void update(int x, int y) {
        for (; x <= m; x += x & -x)
            bits[x] = max(bits[x], y);
    }

public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        const int n = scores.size();
        vector<int> rank(n);
        for (int i = 0; i < n; i++)
            rank[i] = i;

        sort(rank.begin(), rank.end(), [&](int x, int y){
            if (scores[x] != scores[y])
                return scores[x] < scores[y];
            return ages[x] < ages[y];
        });

        m = 1000;
        bits.resize(m + 1, 0);

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int tot = query(ages[rank[i]]);
            update(ages[rank[i]], tot + scores[rank[i]]);
            ans = max(ans, tot + scores[rank[i]]);
        }

        return ans;
    }
};