Best Team With No Conflicts

medium array dp sorting

Problem

You are given scores and ages of n players. A team has a conflict if a younger player has a strictly higher score than an older one. Return the maximum total score of a conflict-free team.

Inputscores = [1,3,5,10,15], ages = [1,2,3,4,5]

Output34

Pick everyone; sorted by age the scores are already non-decreasing.

scores

ages

def best_team_score(scores, ages):
    players = sorted(zip(ages, scores))
    n = len(players)
    dp = [s for _, s in players]
    for i in range(n):
        for j in range(i):
            if players[j][1] <= players[i][1]:
                dp[i] = max(dp[i], dp[j] + players[i][1])
    return max(dp)

function bestTeamScore(scores, ages) {
  const n = scores.length;
  const p = scores.map((s, i) => [ages[i], s]).sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  const dp = p.map(x => x[1]);
  for (let i = 0; i < n; i++)
    for (let j = 0; j < i; j++)
      if (p[j][1] <= p[i][1])
        dp[i] = Math.max(dp[i], dp[j] + p[i][1]);
  return Math.max(...dp);
}

class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        int[][] p = new int[n][2];
        for (int i = 0; i < n; i++) { p[i][0] = ages[i]; p[i][1] = scores[i]; }
        Arrays.sort(p, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        int[] dp = new int[n];
        int best = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = p[i][1];
            for (int j = 0; j < i; j++)
                if (p[j][1] <= p[i][1])
                    dp[i] = Math.max(dp[i], dp[j] + p[i][1]);
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

int bestTeamScore(vector<int>& scores, vector<int>& ages) {
    int n = scores.size();
    vector<pair<int,int>> p(n);
    for (int i = 0; i < n; i++) p[i] = {ages[i], scores[i]};
    sort(p.begin(), p.end());
    vector<int> dp(n);
    int best = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = p[i].second;
        for (int j = 0; j < i; j++)
            if (p[j].second <= p[i].second)
                dp[i] = max(dp[i], dp[j] + p[i].second);
        best = max(best, dp[i]);
    }
    return best;
}

Explanation

A team has a conflict when a younger player out-scores an older one. So if we line players up by age, a valid team is just a subsequence whose scores are non-decreasing — this is a max-sum version of longest increasing subsequence.

First we sort players by (age, score) with sorted(zip(ages, scores)). Sorting ties by score too means equal-age players with lower scores come first, so picking them in order never creates a conflict.

Then dp[i] is the best total score of a conflict-free team that ends with player i. It starts as just that player's own score.

For each earlier player j whose score is <= player i's, we can safely append i after j's team, giving dp[i] = max(dp[i], dp[j] + score[i]). The answer is the largest dp value over all players.

Example: scores = [1,3,5,10,15], ages = [1,2,3,4,5]. Sorted by age the scores are already non-decreasing, so the whole team is valid and the total is 1+3+5+10+15 = 34.

Time: O(n²) Space: O(n)