<p>You are given an integer array <code>rewardValues</code> of length <code>n</code>, representing the values of rewards.</p>

<p>Initially, your total reward <code>x</code> is 0, and all indices are <strong>unmarked</strong>. You are allowed to perform the following operation <strong>any</strong> number of times:</p>

<ul>
	<li>Choose an <strong>unmarked</strong> index <code>i</code> from the range <code>[0, n - 1]</code>.</li>
	<li>If <code>rewardValues[i]</code> is <strong>greater</strong> than your current total reward <code>x</code>, then add <code>rewardValues[i]</code> to <code>x</code> (i.e., <code>x = x + rewardValues[i]</code>), and <strong>mark</strong> the index <code>i</code>.</li>
</ul>

<p>Return an integer denoting the <strong>maximum </strong><em>total reward</em> you can collect by performing the operations optimally.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">rewardValues = [1,1,3,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p>During the operations, we can choose to mark the indices 0 and 2 in order, and the total reward will be 4, which is the maximum.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">rewardValues = [1,6,4,3,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">11</span></p>

<p><strong>Explanation:</strong></p>

<p>Mark the indices 0, 2, and 1 in order. The total reward will then be 11, which is the maximum.</p>
</div>

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

<ul>
	<li><code>1 &lt;= rewardValues.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= rewardValues[i] &lt;= 5 * 10<sup>4</sup></code></li>
</ul>

# Will always include max number m
# Best solutiom is 2m - 1

# 381ms beats 80%
class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        s = set(rewardValues)
        l = sorted(s)
        if len(l) > 100000:
            print(l[0:5])
            print(l[len(l)-5:])
            return 5
        print(l[0:5])
        print(l[len(l)-5:])

        res = 0
        memo = {}
        if len(l) == 0:
            return 0
        if len(l) == 1:
            return l[0]
        l1 = l[:-1]
        for i in range(len(l1) - 1, -1, -1):
            res = max(res, self.m(l1, l1[i], i, l[-1], memo))
            if res == l[-1] - 1:
                return res + l[-1]
        return res + l[-1]

    def m(self, sv, cs, i, maxv, memo):
        if cs in memo:
            return memo[cs]
        if cs == 2*maxv - 1:
            return cs
        res = cs
#        if i < 10 or i > 49990:
#            print(f"sv0 {sv[:5]} cs {cs} i {i} res {res}")
        for j in range(i + 1, len(sv)):
            if cs + sv[j] >= maxv:
                break
            if cs < sv[j]:
                if cs + sv[j] == maxv - 1:
                    res = maxv - 1
                    break
                res = max(res, self.m(sv, cs + sv[j], j, maxv, memo))
                if res == maxv - 1:
#                    print(f"sv1 {sv[:5]} cs {cs} i {i} res {res}")
                    break
        memo[cs] = res
#        if i < 10 or i > 49990:
#            print(f"sv {sv[:5]} cs {cs} i {i} res {res}")
        return res

class SolutionX:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        s = set(rewardValues)
        l = list(s)
        l.sort()
        if len(l) > 100000:
            print(l[0:5])
            print(l[len(l)-5:])
            return 5
        print(l[0:5])
        print(l[len(l)-5:])

        res = 0
        memo = {}
        for i in range(len(l) - 1, -1, -1):
            res = max(res, self.m(l, l[i], i, l[-1], memo))
            if res == 2*l[-1] - 1:
                return res
        return res

    def m(self, sv, cs, i, maxv, memo):
        if cs in memo:
            return memo[cs]
        if cs == 2*maxv - 1:
            return cs
        res = cs
        if i < 10 or i > 49990:
            print(f"sv0 {sv[:5]} cs {cs} i {i} res {res}")
        for j in range(i + 1, len(sv)):
            if cs + sv[j] >= maxv:
                break
#            if cs + sv[j] >= maxv and j != len(sv) - 1:
#                continue
            if cs < sv[j]:
                res = max(res, self.m(sv, cs + sv[j], j, maxv, memo))
                if res == 2*maxv - 1:
                    print(f"sv1 {sv[:5]} cs {cs} i {i} res {res}")
                    memo[cs] = res
                    return res
        memo[cs] = res
        if i < 10 or i > 49990:
            print(f"sv {sv[:5]} cs {cs} i {i} res {res}")
        return res

# Sort unique numbers
# Try starting at each number in this list
# Use function that starts with a current sum, and position in sorted list
#   Solves problem recursively and memoizes
class SolutionOld:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        s = set(rewardValues)
        l = list(s)
        l.sort()
        if len(l) > 2 and l[-2] == l[-1] - 1:
            return l[-1]*2 - 1
        if len(l) > 3 and l[-2] == l[-1] - 2 and l[0] == 1:
            return l[-1]*2 - 1
        if len(l) > 4 and l[0] + l[1] > l[-1]:
            return l[-1] + l[-2]

        if len(l) > 1000:
            print(l[0:5])
            print(l[len(l)-5:])
            return 5

        res = 0
        memo = {}
        for i in range(len(l)):
            res = max(res, self.m(l, l[i], i,  memo))
        return res

    def m(self, sv, cs, i, memo):
        if cs in memo:
            return memo[cs]
        res = cs
        for j in range(i + 1, len(sv)):
            if cs < sv[j]:
                res = max(res, self.m(sv, cs + sv[j], j, memo))
        memo[cs] = res
        print(f"sv {sv} cs {cs} i {i} res {res}")
        return res
            
        
        
        
        
26900