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 <= 5 * 1041 <= rewardValues[i] <= 5 * 104Problem Overview: You are given an array of reward values. Start with a total reward of 0. You may pick any value v only if v > currentTotal. After picking it, the total becomes currentTotal + v. The goal is to maximize the final total reward after performing any number of valid operations.
The constraint that a value must be strictly greater than the current total makes brute force ordering expensive. Once the running total grows, many smaller values become unusable. Efficient solutions focus on processing rewards in sorted order and tracking which totals are achievable.
Approach 1: Greedy Approach Using Sorting (O(n log n + k²) time, O(k) space)
Sort the reward values and remove duplicates. Maintain a set of achievable totals starting with {0}. For each reward v, iterate over the current totals and only extend those where total < v. Each valid extension produces a new total total + v. Add these new totals back to the set. The key observation: if the current total is already ≥ v, you cannot take v anymore, so those states are ignored. This behaves like a subset construction where each reward can be used at most once under the strict inequality constraint. Sorting ensures smaller rewards are considered first, which naturally respects the operation rule. The method is straightforward but the state set can grow large, making it slower for bigger inputs.
Approach 2: Dynamic Programming with Memoization / Bitset Optimization (O(n log n + M / word) time, O(M) space)
A more scalable strategy treats the problem as a subset-sum style DP. Let dp[x] indicate whether a total reward x is achievable. Start with dp[0] = true. After sorting the rewards, process each value v. Only totals strictly less than v can transition, so shift the reachable states by v but mask out all states ≥ v. In practice this is implemented using a bitset: take the bitset of reachable sums, keep only bits < v, shift left by v, and OR it with the original bitset. This compact representation allows thousands of sums to be updated in a single machine operation. The maximum possible reward is bounded (roughly under twice the maximum element), so the bitset stays manageable.
This technique heavily relies on ideas from dynamic programming and bit manipulation. Sorting the input array first simplifies the transition logic and ensures rewards are processed in increasing order, which is common when working with constrained subsets of an array.
Recommended for interviews: The DP/bitset solution is the expected optimal answer. A brute-force or naive greedy explanation shows you understand the constraint v > currentTotal, but the optimized DP demonstrates the ability to convert the problem into a subset-sum style state transition and reduce complexity with bit operations.
This approach involves sorting the array and greedily adding rewards to the total reward when possible. The idea is to maximize the total reward by always trying to add the smallest available reward greater than our current total reward, thereby allowing us larger potential future additions after sorting the array in ascending order.
This C program sorts the input array of rewards in ascending order using `qsort`. It then iterates through the sorted array, adding a reward to the total if it is greater than the current total reward.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) additional space complexity.
This approach uses dynamic programming to explore and memoize states defined by the current reward accumulated and remaining unmarked indices. We can recursively decide whether to include a certain reward based on the current total using memoization to avoid redundant calculations.
The C code involves recursive dynamic programming with memoization to compute the maximum total reward by exploring whether to take a reward or skip it. The dp array and rewards array are used to store intermediate results and avoid recalculations.
Time Complexity: O(n^2) due to the nested structure of considering each reward with possible options.
Space Complexity: O(n) for the memoization table.
| Approach | Complexity |
|---|---|
| Greedy Approach Using Sorting | Time Complexity: O(n log n) due to sorting. |
| Dynamic Programming with Memoization | Time Complexity: O(n^2) due to the nested structure of considering each reward with possible options. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting and Reachable Set | O(n log n + k²) | O(k) | Good for understanding the state transitions and constraints. Works for smaller inputs. |
| Dynamic Programming with Bitset | O(n log n + M / word) | O(M) | Optimal approach when reward values are large. Bit operations update many states at once. |
| DP with Memoization (Recursive) | O(n * M) | O(n * M) | Useful for reasoning about the decision process (pick vs skip) before optimizing to bitset. |
3181 & 3180 | BitSet Crash Course | DP | 3181. Maximum Total Reward Using Operations II & I • Aryan Mittal • 8,724 views views
Watch 9 more video solutions →Practice Maximum Total Reward Using Operations II with our built-in code editor and test cases.
Practice on FleetCode