1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int[][] scoreAgePair = new int[scores.length][2];
        for (int i = 0; i < scoreAgePair.length; i++) {
            scoreAgePair[i][0] = scores[i];
            scoreAgePair[i][1] = ages[i];
        }
        Arrays.sort(scoreAgePair, (a, b) -> a[1] != b[1] ? a[1] - b[1] : a[0] - b[0]);
        int[] dp = new int[scoreAgePair.length];
        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            dp[i] = scoreAgePair[i][0];
            for (int j = 0; j < i; j++) {
                if (scoreAgePair[j][0] <= scoreAgePair[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + scoreAgePair[i][0]);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

首先是把score和age构成pair然后sort一下. 使得pair是按年龄从小到大排. 如果年龄相同, 那么按照分数从小到大排. 之后我们使用dp来存这个信息: dp[i]表示包含当前score的前提下挑选之前的球员能达到最大值的调法产生的最大值是多少. 这样当我们知道i之前每个位置能产生的最大值后, 我们通过比较当前位置和之前每个位置的score的大小来确保age大score也要大. 满足这个条件后看一下它那个位置的最大score加上现在位置的score是否能产生当前位置的最大值.

需要注意的是我们必须在age相同时根据score大小进行排序. 因为如果相同age但是score大的靠前的话, 相同的age无法把所有的score都包含. 比如age都是1, 但是score大的在前, 那么当我们在score小的位置时我们看到score大的在前比我们大, 那么就会选择不包含这个score大的, 但是其实这个score大的位置的age和我们一样, 我们是可以包含的.

本题的关键就是包含某个球员的前提下能够凑成的最大值是多少. 我们通过sort以及double for loop构建了这个dp数组. sort必须按照age以及age相同时score的标准去排列, 这样才能得到包含某个球员的前提下最大值的正确值.

时间复杂度: O(n^2)
空间复杂度: O(n)