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:
i from the range [0, n - 1].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 <= 20001 <= rewardValues[i] <= 2000Problem Overview: You receive an array rewardValues. You may repeatedly pick an element only if its value is strictly greater than your current total reward. After picking it, the value is added to the total and the element becomes unusable. The goal is to maximize the final reward.
The constraint rewardValues[i] > currentSum creates an ordering dependency. Picking a value increases the sum, which may block other elements later. The core challenge is exploring valid reward sums without testing every permutation.
Approach 1: Greedy + Dynamic Programming with Sorting (O(n * M) time, O(M) space)
Sort the array first. Processing smaller rewards earlier gives you more opportunities to build valid intermediate sums. Maintain a boolean DP array (or bitset) where dp[s] means a total reward s is achievable. For each value v, iterate through all reachable sums s where s < v. If that condition holds, you can transition to s + v. Sorting ensures you always evaluate candidates in increasing order, which keeps the valid state space compact. The maximum reachable sum in the DP array becomes the answer. Time complexity is O(n * M), where M is the maximum reachable reward sum (bounded by roughly twice the largest value). Space complexity is O(M).
This approach blends array processing with dynamic programming. The greedy part (sorting) reduces invalid combinations, while DP tracks all feasible totals.
Approach 2: Iterative State Expansion Without Sorting (O(n * M) time, O(M) space)
Instead of sorting, maintain a set or boolean structure representing all reachable reward sums. For each value v, scan the current states and create new sums s + v only if s < v. Store the newly formed states separately and merge them into the global set afterward to avoid interfering with the same iteration. This effectively performs state expansion similar to subset-sum DP but with the additional constraint that the previous sum must be smaller than the chosen value.
This version keeps the algorithm purely iterative and avoids sorting, but it may process more intermediate states because values are not ordered. Time complexity remains O(n * M) with O(M) space, where M is the maximum tracked sum. It still relies heavily on dynamic programming state transitions.
Recommended for interviews: The sorted DP approach. Interviewers expect you to recognize the monotonic constraint (value > currentSum) and reduce permutations using sorting. Starting with a brute-force idea shows understanding of the rule, but the DP optimization demonstrates strong problem-solving and state modeling skills.
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.
Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(1), as the sorting can be done in place.
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.
Time Complexity: O(n^2), since each element is checked potentially up to n times.
Space Complexity: O(n) for the boolean tracking array.
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:
rewardValues array for the index i of the first element greater than x;rewardValues array starting from index i, and for each element v, calculate the maximum value of v + dfs(x + v).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.
Python
Java
C++
Go
TypeScript
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 M$ is twice the maximum value in the rewardValues array, and rewardValues array.
Python
Java
C++
Go
TypeScript
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach Using Sorting | Time Complexity: O(n log n), due to the sorting step. |
| Iterative Approach Without Sorting | Time Complexity: O(n^2), since each element is checked potentially up to n times. |
| Sorting + Memoization + Binary Search | — |
| Dynamic Programming | — |
| Dynamic Programming + Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy + DP with Sorting | O(n * M) | O(M) | Best general solution. Sorting reduces invalid states and keeps transitions efficient. |
| Iterative State Expansion (No Sorting) | O(n * M) | O(M) | Useful when preserving original order or when sorting is restricted. |
3181 & 3180 | BitSet Crash Course | DP | 3181. Maximum Total Reward Using Operations II & I • Aryan Mittal • 9,799 views views
Watch 9 more video solutions →Practice Maximum Total Reward Using Operations I with our built-in code editor and test cases.
Practice on FleetCode