1626. Best Team With No Conflicts

Link

Solution

   public int bestTeamScore(int[] scores, int[] ages) {
        int N = ages.length;
        int[][] candidates = new int[N][2];
        for(int i = 0; i < N; i++){
            candidates[i][0] = scores[i];
            candidates[i][1] = ages[i];
        }
        
        Arrays.sort(candidates, (a,b)-> a[1]==b[1] ? a[0] - b[0] : a[1] - b[1]);
        int ret = 0;
        int[] dp = new int[N]; //dp[i] : the max score witch ends in candidates[i]
        for(int i = 0; i < N; i++){
            
            dp[i] = candidates[i][0];
            
            for(int j = 0 ; j < i; j++){
                if(candidates[j][0] <= candidates[i][0]){
                    dp[i] = Math.max(dp[i], dp[j] + candidates[i][0]);
                }
            }
            
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }