Maximum Total Reward Using Operations I - Solution & Explanation

Sort the reward values in ascending order and iterate over them. At each step, if the current reward value is greater than the current total, add it to the total. This approach maximizes the reward by always adding the smallest possible value that increases the total, ensuring potential larger values can be added later.

First we sort the array of rewards using Quicksort. Then, we iterate through the sorted array, adding each reward to the total if it is greater than the current total. This greedy approach ensures that the total reward is maximized by always choosing the next feasible smallest reward.

This approach iteratively chooses the largest value that can be added to the current total without sorting first. It utilizes a set or a boolean array to ensure indices are marked and not reused. This can potentially be less optimal than sorting but saves space used by sorting operations.

An array is used for tracking marked indices, and we iterate over the reward values array, choosing the largest suitable value in each iteration to add to the total. Although each iteration involves an entire loop over the array, it carefully selects the most beneficial option available.

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

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

The execution process of the function 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 + 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.

We define f[i][j] as whether it is possible to obtain a total reward of j using the first i reward values. Initially, f[0][0] = True, and all other values are False.

We consider the i-th reward value v. If we do not choose it, then f[i][j] = f[i - 1][j]. If we choose it, then f[i][j] = f[i - 1][j - v], where 0 leq j - v < v. Thus, the state transition equation is:

$ f[i][j] = f[i - 1][j] \vee f[i - 1][j - v]

The final answer is max{j \mid f[n][j] = True}.

Since f[i][j] only depends on f[i - 1][j] and f[i - 1][j - v], we can optimize away the first dimension and use only a one-dimensional array for state transitions.

The time complexity is O(n times 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.

We can optimize Solution 2 by defining a binary number f to save the current state, where the i-th bit of f being 1 indicates that a total reward of i is reachable.

Observing the state transition equation from Solution 2, f[j] = f[j] \vee f[j - v], this is equivalent to taking the lower v bits of f, shifting them left by v bits, and then performing an OR operation with the original f.

Thus, the answer is the position of the highest bit in f.

The time complexity is O(n times M / w), and the space complexity is O(n + M / w). Where n is the length of the rewardValues array, M is twice the maximum value in the rewardValues array, and the integer w = 32 or 64.