1626. Best Team With No Conflicts

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        """tc O(N^2) sc O(N)
        main idea: LIS 
        dp[i]: max total scores by sorted ages[i]
        1. sort age,score pair by age
        2. at any age[i], find age[j] where score[j] <= score[i] and j < i 
        3.  update number of maxscore 
        """
        age_score = [[age, score] for age,score in zip(ages,scores)]
        age_score.sort() # sort by age in ascending order 
        dp = [score for _, score in age_score]
        max_score_sum = 0 
        for i in range(len(ages)):
            for j in range(i):
                if age_score[i][1] >= age_score[j][1]:
                    dp[i] = max(dp[i], dp[j] + age_score[i][1])   
            max_score_sum = max(max_score_sum, dp[i])
        return max_score_sum

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        """tc O(NlgN+1000N ) sc O(1000)
        main idea: loop score from low to high, find max total scores before current age (included)
        1. create an array by age:   to get max score sum by age_i 
        2. sort score, age tuple by score in ascending order 
        3. calculate max scores by far (including current age) with current score 
        4. get max total score if max scores is bigger than the global max res 
        """
        max_scores_before_age = [0] *1001
        
        res = 0#print(sorted(zip(scores,ages)))
        for score, age in sorted(zip(scores, ages)):
            max_score_age_capped[age] = score + max(max_score_age_capped[:age+1])
            if max_score_age_capped[age] > res:
                res = max_score_age_capped[age]
        return res