LeetCode 1626. The best team without contradiction

Problem description

Suppose you are the manager of the team . For the upcoming tournament , You want to form a team with the highest overall score . The score of a team is the score of all the players in the team The sum of the .

However , Contradictions in the team will limit the players' play , So you have to choose one There is no contradiction The team of . If a younger player's score Strictly greater than An older player , There are contradictions . There will be no contradiction between players of the same age .

Here are two lists scores and ages, Each group scores[i] and ages[i] It means the first one i Score and age of players . Please return The highest score of all possible non contradictory teams .

Example 1：

Input ：scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output ：34
explain ： You can select all players .
Example 2：

Input ：scores = [4,5,6,5], ages = [2,1,2,1]
Output ：16
explain ： The best choice is after 3 player . Be careful , You can select multiple players of the same age .
Example 3：

Input ：scores = [1,2,3,5], ages = [8,9,10,1]
Output ：6
explain ： The best choice is before 3 player .
 

Tips ：

1 <= scores.length, ages.length <= 1000
scores.length == ages.length
1 <= scores[i] <= 106
1 <= ages[i] <= 1000

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/best-team-with-no-conflicts
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Java

class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        int[][] player = new int[n][2];// Age and score 
        for(int i = 0;i < n;i++){
            player[i][0] = ages[i];
            player[i][1] = scores[i];
        }
        // Sort 
        Arrays.sort(player,(a,b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

        
        int[] dp = new int[n];
        dp[0] = player[0][1];
        int ans = dp[0];
        
        for(int i = 1;i < n;i++){
            dp[i] = player[i][1];
            for(int j = 0;j < i;j++){
                // Without conflict 
                if(!(player[i][0] > player[j][0] && player[i][1] < player[j][1])){
                    dp[i] = Math.max(dp[i],dp[j] + player[i][1]);
                }
            }
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
}