1626. Best Team With No Conflicts

Option 1: DP

most intuitive approach
T = O(N^2)

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        n = len(scores)
        players = [(age, score) for age, score in zip(ages, scores)]
        players.sort()
        
        dp = []
        for i in range(n):
            dp.append(players[i][1])
            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)

Option 2: optimized DP

T = O(N * MAX_AGE) much faster since MAX_AGE is much less than N
max_scores[age] = score + max(max_scores[:age + 1])
- max(max_scores[:age + 1]) can be either a player with (smaller age + smaller_or_equal score) or (same age + smaller_or_equal score)

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
      
        max_scores=[0] * (max(ages) + 1)
        
        for score, age in sorted(zip(scores, ages)): 
            max_scores[age] = score + max(max_scores[:age + 1])

        return max(max_scores)

Option 3: BIT

how does this work?

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        players = sorted(zip(scores, ages))
        
        dp = [0] * (max(ages))
        
        for score, age in players:
		
			#query the max score
            m = 0
            i = age
            while i > 0:
                m = max(m, dp[i-1])
                i -= i&(-i)
            dp[age-1] = m+score

			# update the tree
            i = age
            while i <= len(dp):
                dp[i-1] = max(dp[age-1], dp[i-1])
                i += i&(-i)
            
        return max(dp)

1626. Best Team With No Conflicts - cocoder39/coco39_LC GitHub Wiki