Maximum Total Reward Using Operations I — Problem & Solution
Maximum Total Reward Using Operations I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Total Reward Using Operations I is a medium coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Bit Manipulation
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array rewardValues of length n. Your total reward x starts at 0, and every index starts unmarked.
You may repeat the following operation any number of times: choose an unmarked index i; if rewardValues[i] is strictly greater than your current total x, add it to x (x = x + rewardValues[i]). Either way, mark index i.
Return the maximum total reward you can collect by performing the operations optimally.
Example 1
Input: rewardValues = [1,1,3,3]
Output: 4
Explanation: Take a 1 (x = 1), then a 3 (x = 4). The other 1 and 3 are no longer larger than x.
Example 2
Input: rewardValues = [1,6,4,3,2]
Output: 11
Explanation: Take 1, then 4 (x = 5), then 6 (x = 11). Taking 1, 2 and 4 instead reaches 7 and blocks the 6.
Example 3
Input: rewardValues = [7]
Output: 7
Constraints
1 <= rewardValues.length <= 20001 <= rewardValues[i] <= 2000
Hints for Maximum Total Reward Using Operations I
Hint 1
Any set of rewards you collect can be collected in increasing order, and that order works exactly when each value exceeds the sum of the smaller chosen ones.
Hint 2
So sort the values and decide, in increasing order, which to take. The state is just the current total
x.Hint 3
Every reachable total is below
2 · max(rewardValues). Keep a boolean array of reachable totals; a valuevcan be added to any reachable totalx < v, givingx + v.
How to solve Maximum Total Reward Using Operations I
Collect rewards in increasing order — any feasible set stays feasible in that order. Then it is a reachability DP over the running total, which never exceeds 2 · max − 1 (the last value added is at most the max, and the total before it is smaller than that value).
Approach
- Sort the distinct values ascending. Let
Mbe the largest; makereach[0..2M-1]with onlyreach[0] = true. - For each value
vin order, for every totalx < vwithreach[x], setreach[x + v] = true. - Return the largest
xwithreach[x].
Why it works
If a set can be collected in some order, then in that order each element exceeds the sum of everything before it, including every smaller element of the set — so increasing order works too. Processing values in increasing order and only adding v to totals below v is exactly that rule. Duplicates never help (a second copy of v would need x < v after already adding v), so distinct values suffice. Totals written by v are at least v, above the totals it reads, so one pass per value does not reuse v.
Complexity
- Time —
O(n log n + n · M) - Space —
O(M)
Pitfalls
- The condition is strictly greater: a value equal to the current total cannot be taken.
- Taking values greedily from smallest up is not optimal — skipping small values can unlock a larger one.
- A bitset (a big integer in Python) speeds the inner loop up by a word size; that is what the harder version of this problem needs.
Reference solution
Python
from typing import List
def maxTotalReward(rewardValues: List[int]) -> int:
reach = 1 # bit x set <=> total x is reachable
for v in sorted(set(rewardValues)):
reach |= (reach & ((1 << v) - 1)) << v
return reach.bit_length() - 1Java
public static int maxTotalReward(int[] rewardValues) {
int[] vals = rewardValues.clone();
Arrays.sort(vals);
int M = vals[vals.length - 1];
boolean[] reach = new boolean[2 * M];
reach[0] = true;
for (int i = 0; i < vals.length; i++) {
int v = vals[i];
if (i > 0 && v == vals[i - 1]) continue;
for (int x = 0; x < v; x++) if (reach[x]) reach[x + v] = true;
}
for (int x = 2 * M - 1; x >= 0; x--) if (reach[x]) return x;
return 0;
}C++
int maxTotalReward(vector<int>& rewardValues) {
vector<int> vals = rewardValues;
sort(vals.begin(), vals.end());
int M = vals.back();
vector<char> reach(2 * M, 0);
reach[0] = 1;
for (int i = 0; i < (int) vals.size(); i++) {
int v = vals[i];
if (i > 0 && v == vals[i - 1]) continue;
for (int x = 0; x < v; x++) if (reach[x]) reach[x + v] = 1;
}
for (int x = 2 * M - 1; x >= 0; x--) if (reach[x]) return x;
return 0;
}JavaScript
var maxTotalReward = function(rewardValues) {
var vals = rewardValues.slice().sort(function(a, b) { return a - b; });
var M = vals[vals.length - 1];
var reach = new Array(2 * M).fill(false);
reach[0] = true;
for (var i = 0; i < vals.length; i++) {
var v = vals[i];
if (i > 0 && v === vals[i - 1]) continue;
for (var x = 0; x < v; x++) if (reach[x]) reach[x + v] = true;
}
for (var x = 2 * M - 1; x >= 0; x--) if (reach[x]) return x;
return 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming