1626. 无矛盾的最佳球队Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

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

给你两个列表 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

# 思路

LIS 排序 + 枚举

# 解法

class Solution {
public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        int[][] ans = new int[n][];
        for (int i = 0; i < n; i++) {
            ans[i] = new int[]{ages[i], scores[i]};
        }
        Arrays.sort(ans, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] > o2[1] ? 1 : -1;
            }
            return o1[0] > o2[0] ? 1 : -1;
        });
        scores[0] = ans[0][1];
        int MAX = scores[0];
        for (int i = 1; i < n; i++) {
            int max = ans[i][1];
            for (int j = 0; j < i; j++) {
                if (ans[i][1] >= ans[j][1]) {
                    max = Math.max(scores[j] + ans[i][1], max);
                }
            }
            scores[i] = max;
            MAX = Math.max(max, MAX);
        }
        return MAX;
    }
}

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
26
27
28
29

# 总结

分析出几种情况，然后分别对各个情况实现

#Java