Maximum Total Reward Using Operations I - Video Solutions

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