Formatted question description: https://leetcode.ca/all/1626.html

# 1626. Best Team With No Conflicts (Medium)

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

However, the basketball team is not allowed to have **conflicts**. A **conflict** exists if a younger player has a **strictly higher** score than an older player. A conflict does **not** occur between players of the same age.

Given two lists, `scores`

and `ages`

, where each `scores[i]`

and `ages[i]`

represents the score and age of the `i`

player, respectively, return ^{th}*the highest overall score of all possible basketball teams*.

**Example 1:**

Input:scores = [1,3,5,10,15], ages = [1,2,3,4,5]Output:34Explanation:You can choose all the players.

**Example 2:**

Input:scores = [4,5,6,5], ages = [2,1,2,1]Output:16Explanation:It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.

**Example 3:**

Input:scores = [1,2,3,5], ages = [8,9,10,1]Output:6Explanation:It is best to choose the first 3 players.

**Constraints:**

`1 <= scores.length, ages.length <= 1000`

`scores.length == ages.length`

`1 <= scores[i] <= 10`

^{6}`1 <= ages[i] <= 1000`

**Related Topics**:

Dynamic Programming

## Solution 1. DP

First, sort the players such that they are sorted in ascending order of age, then in ascending order of score.

Let `dp[i]`

be the maximum score we can get if we choose from `0`

th to `i`

th player and must pick `i`

th player.

For `dp[i]`

, we can check each player `j`

(`0 <= j < i`

) whose age must be the same or less than player `i`

, and if their ages are the same, player `j`

’s score must be smaller.

So as long as player `j`

’s score is smaller or equal to player `i`

’s score, we can extend the team with player `i`

based on the optimal solution of `dp[j]`

.

```
dp[i] = max( dp[j] | 0 <= j < i && scores[j] <= scores[i] ) + scores[i]
```

```
// OJ: https://leetcode.com/problems/best-team-with-no-conflicts/
// Time: O(N^2)
// Space: O(N)
// Ref: https://leetcode.com/problems/best-team-with-no-conflicts/discuss/899475/Fairly-easy-DP
class Solution {
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
vector<pair<int, int>> A;
int N = scores.size(), ans = 0;
vector<int> dp(N);
for (int i = 0; i < N; ++i) A.emplace_back(ages[i], scores[i]);
sort(begin(A), end(A));
for (int i = 0; i < N; ++i) {
auto [age, score] = A[i];
for (int j = 0; j < i; ++j) {
if (A[j].second <= score) dp[i] = max(dp[i], dp[j]);
}
ans = max(ans, dp[i] += score);
}
return ans;
}
};
```

Java

```
class Solution {
public int bestTeamScore(int[] scores, int[] ages) {
int length = scores.length;
int[][] scoresAges = new int[length][2];
for (int i = 0; i < length; i++) {
scoresAges[i][0] = scores[i];
scoresAges[i][1] = ages[i];
}
Arrays.sort(scoresAges, new Comparator<int[]>() {
public int compare(int[] scoreAge1, int[] scoreAge2) {
if (scoreAge1[0] != scoreAge2[0])
return scoreAge2[0] - scoreAge1[0];
else
return scoreAge2[1] - scoreAge1[1];
}
});
Map<Integer, List<Integer>> conflictMap = new HashMap<Integer, List<Integer>>();
for (int i = 1; i < length; i++) {
List<Integer> conflictList = new ArrayList<Integer>();
int score = scoresAges[i][0], age = scoresAges[i][1];
for (int j = 0; j < i; j++) {
if (scoresAges[j][0] == score)
break;
if (scoresAges[j][1] > age)
conflictList.add(j);
}
conflictMap.put(i, conflictList);
}
int[][] dp = new int[length][2];
dp[0][0] = 0;
dp[0][1] = scoresAges[0][0];
for (int i = 1; i < length; i++) {
int score = scoresAges[i][0], age = scoresAges[i][1];
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = score;
for (int j = 0; j < i; j++) {
if (age <= scoresAges[j][1])
dp[i][1] = Math.max(dp[i][1], dp[j][1] + score);
}
}
return Math.max(dp[length - 1][0], dp[length - 1][1]);
}
}
```