Best Team With No Conflicts
1 min readJun 28, 2021
Same as LIS, Here instead of maximum length of increasing subsequence, we need to find the maximum sum of increasing subsequence.
We will first sort the array on the basis of ages. Now the score array is same as the nums array given in LIS, the only change is here mums[i]≥ nuts[j];
Here’s the code:
class Solution {
public int bestTeamScore(int[] scores, int[] ages) {
int n=ages.length;
Player[] players= new Player[n];
for(int i=0;i<n;i++){
players[i]=new Player(ages[i],scores[i]);
}
Arrays.sort(players,(a,b)-> b.age==a.age? a.score-b.score : a.age-b.age);
int[] dp = new int[n];
dp[0]=players[0].score;
int max= dp[0];
for(int i = 1; i<n; i++) {
dp[i]=players[i].score;
for(int j =0; j<i; j++) {
if(players[j].score <= players[i].score) {
dp[i] = Math.max(dp[i],players[i].score + dp[j]);
}
}
max = Math.max(dp[i], max);
}
return max;
}
class Player{
int age;
int score;
public Player(int age, int score){
this.age=age;
this.score=score;
}
}
}