Maximum Total Reward Using Operations I

Medium
1657.

Maximum Total Reward Using Operations I

Maximum Total Reward Using Operations I is a medium coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon interviews.

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 <= 2000
  • 1 <= rewardValues[i] <= 2000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} rewardValues
 * @return {number}
 */
var maxTotalReward = function(rewardValues) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 2000
  • 1 <= rewardValues[i] <= 2000

Hints for Maximum Total Reward Using Operations I

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

  2. Hint 2

    So sort the values and decide, in increasing order, which to take. The state is just the current total x.

  3. Hint 3

    Every reachable total is below 2 · max(rewardValues). Keep a boolean array of reachable totals; a value v can be added to any reachable total x < v, giving x + 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

  1. Sort the distinct values ascending. Let M be the largest; make reach[0..2M-1] with only reach[0] = true.
  2. For each value v in order, for every total x < v with reach[x], set reach[x + v] = true.
  3. Return the largest x with reach[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() - 1

Java

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