Best Team With No Conflicts

---

Intuition

• This question builds upon Longest Increasing Subsequence (Coding).
• Only if a player has an age less than another player and a score higher than that player does that player not get added to that specific team.
• In Longest Increasing Subsequence (Coding), we found the count of the longest increasing subsequence. Here, we want the count of the scores of the longest increasing subsequence that does not contain the conflict.
• To do so, first sort the players by age, and keep each player’s corresponding scores. This ensures that we don’t have to deal with a given age being greater than the current player, so we can instead only compare those players with less age with the player of more age.
• The DP array is used for keeping track of the maximum possible sum of scores at that index. As such, at the end of each iteration, DP keeps track of the teams with the maximum possible score seen so far.
  • However, the the current team may not be a part of the previously occurring max based on if there is a conflict, so we have to iterate through all possibilities.
• Note that this question will TLE if attempted to solve in a top down fashion.

Complexity

Runtime

$O(N^2)$ since we have to iterate through an arithmetic series worth of elements.

Space

$O(N)$ due to the dp array

Code

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        players = list(sorted(zip(ages,  scores)))
        dp = [player[1] for player in players]
 
        for i in range(1, len(players)):
            for j in range(i):
                # Conflict
                if players[j][1] > players[i][1]:
                    continue
                
                dp[i] = max(dp[i], players[i][1] + dp[j])
 
        return max(dp)

Notes

Cards

START Basic Front: Best Team With No Conflicts Back: Use Longest Common Subsequence for all subsequences without a conflict. END

---

References

• Best Team With No Conflicts