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

本文主要是介绍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;}
}