<p>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 <strong>sum</strong> of scores of all the players in the team.</p>

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

<p>Given two lists, <code>scores</code> and <code>ages</code>, where each <code>scores[i]</code> and <code>ages[i]</code> represents the score and age of the <code>i<sup>th</sup></code> player, respectively, return <em>the highest overall score of all possible basketball teams</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> scores = [1,3,5,10,15], ages = [1,2,3,4,5]
<strong>Output:</strong> 34
<strong>Explanation:</strong>&nbsp;You can choose all the players.
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> scores = [1,2,3,5], ages = [8,9,10,1]
<strong>Output:</strong> 6
<strong>Explanation:</strong>&nbsp;It is best to choose the first 3 players. 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= scores.length, ages.length &lt;= 1000</code></li>
	<li><code>scores.length == ages.length</code></li>
	<li><code>1 &lt;= scores[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= ages[i] &lt;= 1000</code></li>
</ul>

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        """
        =============
        DO IT AGAIN!!
        =============
        neetcode solution. 
        Recursive with memoization.
        https://www.youtube.com/watch?v=7kURH3btcV4

        Similar to Longest Increasing Subsequence (LIS)

        Sorting based on scores.
        Scores are already increasing order.
        Every time we add a new (next) value,
        the next value should not have lower age.

        DFS(i, j)
        i = what index we are at in scores array
        j = max age we have seen so far 
        --> DP memoization

        Time: O(n^2)
        i can have n values
        j can have n values
        """
        pairs = [
            [scores[i], ages[i]] for i in range(len(scores))
        ]

        # sort by scores
        pairs.sort()
        memo = {} 

        def dfs(i, j):
            """
            :param i: what index we are at in scores array
            :param j: max age we have seen so far 
            """
            # base case: out of bounds
            if i == len(pairs):
                return 0
            
            # base case: memoization
            if (i, j) in memo:
                return memo[(i, j)]

            max_score, max_age = pairs[j] if j >= 0 else [0, 0]
            score, age = pairs[i]
            res = 0 
            if not (score > max_score and age < max_age):
                res = dfs(i+1, i) + score ## add score
            memo[(i, j)] = max(res, dfs(i+1, j))  # skip score
            return memo[(i, j)]

        return dfs(0, -1)

    def bestTeamScore_neetcode(self, scores: List[int], ages: List[int]) -> int:
        """
        neetcode solution. DP tabulation.
        https://www.youtube.com/watch?v=7kURH3btcV4
        """
        pairs = [
            [scores[i], ages[i]] for i in range(len(scores))
        ]

        # sort by scores
        pairs.sort()

        # init the dp 
        dp = [pairs[i][0] for i in range(len(pairs))]

        # 
        for i in range(len(pairs)):
            # as if i has the max_score
            max_score, max_age = pairs[i]
            for j in range(0, i): ## upto i 
                # for every j up to i...
                # age condition
                _, age = pairs[j]
                if max_age >= age:
                    # we are allowed to add the dp[j]
                    dp[i] = max(dp[i], max_score + dp[j])
                else:
                    pass 

        return max(dp)
277600