1626 无矛盾的最佳球队（排序+动态规划）（灵神笔记）

题目

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

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

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

示例 1：

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

输入：scores = [4,5,6,5], ages = [2,1,2,1]
输出：16
解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。
示例 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] <= 106
1 <= ages[i] <= 1000

题解

//令第i个人是球队中下标最大的，i>j，则scores[j]<=scores[j]
//scores[j]<=scores[j],相等则年龄从小到大排序,小于则必须满足age[j]<=age[i]
//因此需要从ages中选择一个得分之和最大的递增子序列（允许有相同元素）

class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length, ans = 0;
        //记录一个下标数组
        var index = new Integer[n];
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        //分数相等的从小到大排序，分数不同同样从小到大排序
        Arrays.sort(index, (i, j) -> scores[i] == scores[j] ? ages[i] - ages[j] : scores[i] - scores[j]);
        int[] f = new int[n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                //f[i]为以age[i]结尾的递增子序列的最大得分
                //f[i]=max(f[j])+scores[i]
                if (ages[index[j]] <= ages[index[i]]) {
                    f[i] = Math.max(f[i], f[j]);
                }
            }
            f[i] += scores[index[i]];
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25