Maximum Total Reward Using Operations II - Solution & Explanation

Problem 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.