Best Team With No Conflicts

Abhinay Gupta
1 min readJun 28, 2021

--

https://leetcode.com/problems/best-team-with-no-conflicts/

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;
}
}
}

--

--

Abhinay Gupta

Exploring personal growth, tech, and culture through engaging storytelling | Inspiring and connecting with readers worldwide.