Best Team With No Conflicts

给两个数组, 一个是score 一个age, 求在没有conflict的情况下的最大score. conflict是两个数组的数, 在同age下的score必须大小严格保持一致.

dp题. 两个可能: 选当前的人或者不选当前的人. 然后求最大的score.

class Solution {
    class Pair{
        int s;
        int a;
        Pair(int s, int a) {
            this.s = s;
            this.a = a;
        }
    }
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        Pair[] pairs = new Pair[n];
        for(int i = 0; i < n; i++) {
            pairs[i] = new Pair(scores[i], ages[i]);
        }
        Arrays.sort(pairs, (a, b) -> (a.a == b.a ? a.s - b.s : a.a - b.a)); 
        int[] dp = new int[n];
        //init dp
        for(int i = 0; i < n; i++) {
            dp[i] = pairs[i].s;
        }
        // dp[i] the max score UNTILL player i which must include the player i 
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(pairs[i].s >= pairs[j].s)
                    dp[i] = Math.max(dp[i], dp[j] + pairs[i].s);
            } 
            res = Math.max(res, dp[i]);
        }
        
        return res;
    }
}