# 3180. Maximum Total Reward Using Operations I

## Description

You are given an integer array rewardValues of length n, representing the values of rewards.

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

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

Return an integer denoting the maximum total reward you can collect by performing the operations optimally.

Example 1:

Input: rewardValues = [1,1,3,3]

Output: 4

Explanation:

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.

Example 2:

Input: rewardValues = [1,6,4,3,2]

Output: 11

Explanation:

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

Constraints:

• 1 <= rewardValues.length <= 2000
• 1 <= rewardValues[i] <= 2000

## Solutions

We can sort the rewardValues array and then use memoization to solve for the maximum total reward.

We define a function $\text{dfs}(x)$, representing the maximum total reward that can be obtained when the current total reward is $x$. Thus, the answer is $\text{dfs}(0)$.

The execution process of the function $\text{dfs}(x)$ is as follows:

1. Perform a binary search in the rewardValues array for the index $i$ of the first element greater than $x$;
2. Iterate over the elements in the rewardValues array starting from index $i$, and for each element $v$, calculate the maximum value of $v + \text{dfs}(x + v)$.
3. Return the result.

To avoid repeated calculations, we use a memoization array f to record the results that have already been computed.

The time complexity is $O(n \times (\log n + M))$, and the space complexity is $O(M)$. Where $n$ is the length of the rewardValues array, and $M$ is twice the maximum value in the rewardValues array.

• class Solution {
private int[] nums;
private Integer[] f;

public int maxTotalReward(int[] rewardValues) {
nums = rewardValues;
Arrays.sort(nums);
int n = nums.length;
f = new Integer[nums[n - 1] << 1];
return dfs(0);
}

private int dfs(int x) {
if (f[x] != null) {
return f[x];
}
int i = Arrays.binarySearch(nums, x + 1);
i = i < 0 ? -i - 1 : i;
int ans = 0;
for (; i < nums.length; ++i) {
ans = Math.max(ans, nums[i] + dfs(x + nums[i]));
}
return f[x] = ans;
}
}

• class Solution {
public:
int maxTotalReward(vector<int>& rewardValues) {
sort(rewardValues.begin(), rewardValues.end());
int n = rewardValues.size();
int f[rewardValues.back() << 1];
memset(f, -1, sizeof(f));
function<int(int)> dfs = [&](int x) {
if (f[x] != -1) {
return f[x];
}
auto it = upper_bound(rewardValues.begin(), rewardValues.end(), x);
int ans = 0;
for (; it != rewardValues.end(); ++it) {
ans = max(ans, rewardValues[it - rewardValues.begin()] + dfs(x + *it));
}
return f[x] = ans;
};
return dfs(0);
}
};

• class Solution:
def maxTotalReward(self, rewardValues: List[int]) -> int:
@cache
def dfs(x: int) -> int:
i = bisect_right(rewardValues, x)
ans = 0
for v in rewardValues[i:]:
ans = max(ans, v + dfs(x + v))
return ans

rewardValues.sort()
return dfs(0)


• func maxTotalReward(rewardValues []int) int {
sort.Ints(rewardValues)
n := len(rewardValues)
f := make([]int, rewardValues[n-1]<<1)
for i := range f {
f[i] = -1
}
var dfs func(int) int
dfs = func(x int) int {
if f[x] != -1 {
return f[x]
}
i := sort.SearchInts(rewardValues, x+1)
f[x] = 0
for _, v := range rewardValues[i:] {
f[x] = max(f[x], v+dfs(x+v))
}
return f[x]
}
return dfs(0)
}

• function maxTotalReward(rewardValues: number[]): number {
rewardValues.sort((a, b) => a - b);
const search = (x: number): number => {
let [l, r] = [0, rewardValues.length];
while (l < r) {
const mid = (l + r) >> 1;
if (rewardValues[mid] > x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
const f: number[] = Array(rewardValues.at(-1)! << 1).fill(-1);
const dfs = (x: number): number => {
if (f[x] !== -1) {
return f[x];
}
let ans = 0;
for (let i = search(x); i < rewardValues.length; ++i) {
ans = Math.max(ans, rewardValues[i] + dfs(x + rewardValues[i]));
}
return (f[x] = ans);
};
return dfs(0);
}