# 1626. Best Team With No Conflicts     • Time: $O(n^2)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 struct Player { int age; int score; Player(int age, int score) : age(age), score(score) {} }; class Solution { public: int bestTeamScore(vector& scores, vector& ages) { const int n = scores.size(); vector players; // dp[i] := max score of choosing players[0..i] w/ players[i] being selected vector dp(n); for (int i = 0; i < n; ++i) players.emplace_back(ages[i], scores[i]); sort(begin(players), end(players), [](const auto& a, const auto& b) { return a.age == b.age ? a.score > b.score : a.age > b.age; }); for (int i = 0; i < n; ++i) { // For each player, we choose it first dp[i] = players[i].score; // players[j].age >= players[i].age since we sort in descending order // So we only have to check that // players[j].score >= players[i].score for (int j = 0; j < i; ++j) if (players[j].score >= players[i].score) dp[i] = max(dp[i], dp[j] + players[i].score); } return *max_element(begin(dp), end(dp)); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Player { public int age; public int score; public Player(int age, int score) { this.age = age; this.score = score; } }; class Solution { public int bestTeamScore(int[] scores, int[] ages) { final int n = scores.length; Player[] players = new Player[n]; // dp[i] := max score of choosing players[0..i] w/ players[i] being selected int[] dp = new int[n]; for (int i = 0; i < n; ++i) players[i] = new Player(ages[i], scores[i]); Arrays.sort(players, (a, b) -> a.age == b.age ? b.score - a.score : b.age - a.age); for (int i = 0; i < n; ++i) { // For each player, we choose it first dp[i] = players[i].score; // players[j].age >= players[i].age since we sort in descending order // So we only have to check that // players[j].score >= players[i].score for (int j = 0; j < i; ++j) if (players[j].score >= players[i].score) dp[i] = Math.max(dp[i], dp[j] + players[i].score); } return Arrays.stream(dp).max().getAsInt(); } }