3181. Maximum Total Reward Using Operations II Solution

Q: Is Maximum Total Reward Using Operations II easy or hard?

Maximum Total Reward Using Operations II is rated Hard because the naive greedy interpretation fails on edge cases. The correct solution requires recognizing the subset-sum style DP and optimizing it using bit manipulation.

Q: Maximum Total Reward Using Operations II Python/Java solution

Python solutions typically use integers as bitsets or boolean arrays to simulate bit operations. Java and C++ implementations often use BitSet or bitset structures for faster shifting and masking when updating reachable sums.

Q: How to solve Maximum Total Reward Using Operations II in O(n log n)?

Sort the rewards and maintain a bitset representing achievable totals. For each value v, keep only totals smaller than v, shift them by v, and merge with existing states. Bitset operations update multiple sums simultaneously, making the algorithm close to O(n log n) with word-level parallelism.

Q: What is the best approach for Maximum Total Reward Using Operations II?

The most efficient solution uses dynamic programming with a bitset. After sorting the reward values, track reachable reward totals in a bitset and update it by shifting states for each value while keeping only totals smaller than the current reward. This reduces transitions to fast bit operations and handles large inputs efficiently.

Q: Is Maximum Total Reward Using Operations II asked at Google/Amazon/Meta?

Hard dynamic programming and bit manipulation problems similar to this frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests state modeling, subset transitions, and optimization using bitsets or compressed DP.

Q: What data structure is used in Maximum Total Reward Using Operations II?

The optimal solution uses a bitset or boolean DP array to track which reward sums are achievable. Sorting the array and updating states with bit shifts allows efficient subset transitions.

Q: What is the time complexity of Maximum Total Reward Using Operations II?

The optimized bitset dynamic programming solution runs in O(n log n + M / word) time, where n is the number of rewards and M is the maximum possible reward sum tracked by the bitset. Space complexity is O(M) for storing reachable totals.

The problem

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:

Choose an unmarked index i from the range [0, n - 1].
If 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 * 10⁴
1 <= rewardValues[i] <= 5 * 10⁴

Approach overview

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.

Approach 1: Greedy Approach Using Sorting

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.

Python

def max_total_reward(reward_values):
    reward_values.sort()
    x = 0
    for value in reward_values:
        if value > x:
            x += value
    return x

rewards = [1, 6, 4, 3, 2]
print(max_total_reward(rewards))

Java

import java.util.Arrays;

public class MaxTotalReward {
    public int maxTotalReward(int[] rewardValues) {
        Arrays.sort(rewardValues);
        int x = 0;
        for (int value : rewardValues) {
            if (value > x) {
                x += value;
            }
        }
        return x;
    }
    public static void main(String[] args) {
        MaxTotalReward solution = new MaxTotalReward();
        int[] rewards = {1, 6, 4, 3, 2};
        System.out.println(solution.maxTotalReward(rewards));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int maxTotalReward(std::vector<int>& rewardValues) {
    std::sort(rewardValues.begin(), rewardValues.end());
    int x = 0;
    for (int value : rewardValues) {
        if (value > x) {
            x += value;
        }
    }
    return x;
}

int main() {
    std::vector<int> rewards = {1, 6, 4, 3, 2};
    std::cout << maxTotalReward(rewards) << std::endl;
    return 0;
}

JavaScript

function maxTotalReward(rewardValues) {
    rewardValues.sort((a, b) => a - b);
    let x = 0;
    for (let value of rewardValues) {
        if (value > x) {
            x += value;
        }
    }
    return x;
}

const rewards = [1, 6, 4, 3, 2];
console.log(maxTotalReward(rewards));

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int maxTotalReward(int* rewardValues, int n) {
    qsort(rewardValues, n, sizeof(int), compare);
    int x = 0;
    for (int i = 0; i < n; i++) {
        if (rewardValues[i] > x) {
            x += rewardValues[i];
        }
    }
    return x;
}

int main() {
    int rewards[] = {1, 6, 4, 3, 2};
    int n = sizeof(rewards) / sizeof(rewards[0]);
    printf("%d\n", maxTotalReward(rewards, n));
    return 0;
}

using System;

public class MaxTotalReward {
    public int MaxTotalRewardFunc(int[] rewardValues) {
        Array.Sort(rewardValues);
        int x = 0;
        foreach (int value in rewardValues) {
            if (value > x) {
                x += value;
            }
        }
        return x;
    }
    public static void Main() {
        MaxTotalReward solution = new MaxTotalReward();
        int[] rewards = {1, 6, 4, 3, 2};
        Console.WriteLine(solution.MaxTotalRewardFunc(rewards));
    }
}

This Python solution first sorts the list of rewards. As it iterates through the sorted list, it adds a reward to the total if it exceeds the current value of total reward.

Complexity

Time Complexity: O(n log n) due to the use of sorting.
Space Complexity: O(1) additional space.

Try this approach in the editor

Approach 2: Dynamic Programming with Memoization

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.

Python

def max_total_reward(reward_values):
    def helper(index, current):
        if index == len(reward_values):
            return current
        if (index, current) in memo:
            return memo[(index, current)]
        include = current
        if reward_values[index] > current:
            include = helper(index + 1, current + reward_values[index])
        exclude = helper(index + 1, current)
        memo[(index, current)] = max(include, exclude)
        return memo[(index, current)]
    memo = {}
    return helper(0, 0)

rewards = [1, 6, 4, 3, 2]
print(max_total_reward(rewards))

Java

import java.util.*;

public class MaxTotalRewardDP {
    private Map<Integer, Map<Integer, Integer>> dp = new HashMap<>();
    private List<Integer> rewards;

    public int maxTotalReward(List<Integer> rewardValues) {
        this.rewards = rewardValues;
        return calcMaxReward(0, 0);
    }

    private int calcMaxReward(int index, int currReward) {
        if (index >= rewards.size()) return currReward;
        if (dp.containsKey(index) && dp.get(index).containsKey(currReward)) {
            return dp.get(index).get(currReward);
        }
        int include = currReward;
        if (rewards.get(index) > currReward) {
            include = calcMaxReward(index + 1, currReward + rewards.get(index));
        }
        int exclude = calcMaxReward(index + 1, currReward);
        int result = Math.max(include, exclude);

        dp.computeIfAbsent(index, k -> new HashMap<>()).put(currReward, result);
        return result;
    }

    public static void main(String[] args) {
        MaxTotalRewardDP solution = new MaxTotalRewardDP();
        List<Integer> rewards = Arrays.asList(1, 6, 4, 3, 2);
        System.out.println(solution.maxTotalReward(rewards));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> rewards;
unordered_map<int, unordered_map<int, int>> memo;

int calcMaxReward(int index, int currentReward) {
    if (index == rewards.size()) return currentReward;
    if (memo[index].count(currentReward)) return memo[index][currentReward];
    int include = (rewards[index] > currentReward)
                   ? calcMaxReward(index + 1, currentReward + rewards[index])
                   : currentReward;
    int exclude = calcMaxReward(index + 1, currentReward);
    return memo[index][currentReward] = max(include, exclude);
}

int maxTotalReward(vector<int>& rewardValues) {
    rewards = rewardValues;
    return calcMaxReward(0, 0);
}

int main() {
    vector<int> rewardValues = {1, 6, 4, 3, 2};
    cout << maxTotalReward(rewardValues) << endl;
    return 0;
}

JavaScript

function maxTotalReward(rewardValues) {
    const memo = {};

    function helper(index, currentTotal) {
        if (index === rewardValues.length) {
            return currentTotal;
        }
        const key = index + '-' + currentTotal;
        if (memo[key] !== undefined) {
            return memo[key];
        }
        let include = currentTotal;
        if (rewardValues[index] > currentTotal) {
            include = helper(index + 1, currentTotal + rewardValues[index]);
        }
        const exclude = helper(index + 1, currentTotal);
        memo[key] = Math.max(include, exclude);
        return memo[key];
    }

    return helper(0, 0);
}

const rewards = [1, 6, 4, 3, 2];
console.log(maxTotalReward(rewards));

#include <stdio.h>
#include <string.h>

int max(int a, int b) { return a > b ? a : b; }

int dp[50001];
int rewards[50001];

int calcMaxReward(int n, int currReward, int index) {
    if (index == n) return currReward;
    if (dp[index] >= 0 && currReward <= rewards[index]) return currReward + dp[index];
    int newReward = currReward;
    if (rewards[index] > currReward) {
        newReward = calcMaxReward(n, currReward + rewards[index], index + 1);
        dp[index] = max(dp[index], newReward - currReward);
    }
    int skipReward = calcMaxReward(n, currReward, index + 1);
    return max(newReward, skipReward);
}

int maxTotalReward(int* rewardValues, int n) {
    memcpy(rewards, rewardValues, n * sizeof(int));
    memset(dp, -1, sizeof(dp));
    return calcMaxReward(n, 0, 0);
}

int main() {
    int arr[] = {1, 6, 4, 3, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Max Total Reward: %d\n", maxTotalReward(arr, n));
    return 0;
}

using System;
using System.Collections.Generic;

public class MaxTotalRewardDP {
    private Dictionary<(int, int), int> memo = new Dictionary<(int, int), int>();

    public int MaxTotalReward(int[] rewardValues) {
        return CalculateMaxTotalReward(rewardValues, 0, 0);
    }

    private int CalculateMaxTotalReward(int[] rewards, int index, int currentTotal) {
        if (index == rewards.Length) return currentTotal;
        if (memo.ContainsKey((index, currentTotal))) return memo[(index, currentTotal)];

        int addCurrent = currentTotal;
        if (rewards[index] > currentTotal) {
            addCurrent = CalculateMaxTotalReward(rewards, index + 1, currentTotal + rewards[index]);
        }
        int skipCurrent = CalculateMaxTotalReward(rewards, index + 1, currentTotal);

        int result = Math.Max(addCurrent, skipCurrent);

        memo[(index, currentTotal)] = result;
        return result;
    }

    public static void Main(string[] args) {
        MaxTotalRewardDP solution = new MaxTotalRewardDP();
        int[] rewards = {1, 6, 4, 3, 2};
        Console.WriteLine(solution.MaxTotalReward(rewards));
    }
}

This Python function defines a recursive helper within the main function and uses a dictionary for memoization. It calculates the maximum possible reward recursively by deciding at each step whether to include the current reward based on the conditions.

Complexity

Time Complexity: Approx. O(n^2) from evaluating each reward's inclusion/exclusion.
Space Complexity: O(n^2) due to the memo dictionary.

Try this approach in the editor

Approach 3: Dynamic Programming + Bit Manipulation

We define f[i][j] as whether it is possible to obtain a total reward of j using the first i reward values. Initially, f[0][0] = True, and all other values are False.

We consider the i-th reward value v. If we do not choose it, then f[i][j] = f[i - 1][j]; if we choose it, then f[i][j] = f[i - 1][j - v], where 0 leq j - v < v. Thus, the state transition equation is:

$f[i][j] = f[i - 1][j] \vee f[i - 1][j - v]

The final answer is max{j \mid f[n][j] = True}.

Since f[i][j] only depends on f[i - 1][j] and f[i - 1][j - v], we can optimize away the first dimension and use only a one-dimensional array for state transitions. Additionally, due to the large data range of this problem, we need to use bit manipulation to optimize the efficiency of state transitions.

We define a binary number f to save the current state, where the i-th bit of f being 1 indicates that a total reward of i is reachable.

Observing the state transition equation f[j] = f[j] \vee f[j - v], this is equivalent to taking the lower v bits of f, shifting them left by v bits, and then performing an OR operation with the original f.

Thus, the answer is the position of the highest bit in f.

The time complexity is O(n times M / w), and the space complexity is O(n + M / w). Where n is the length of the rewardValues array, M is twice the maximum value in the rewardValues array, and the integer w = 32 or 64$.

TypeScript

function maxTotalReward(rewardValues: number[]): number {
    rewardValues.sort((a, b) => a - b);
    rewardValues = [...new Set(rewardValues)];
    let f = 1n;
    for (const x of rewardValues) {
        const mask = (1n << BigInt(x)) - 1n;
        f = f | ((f & mask) << BigInt(x));
    }
    return f.toString(2).length - 1;
}

func maxTotalReward(rewardValues []int) int {
	slices.Sort(rewardValues)
	rewardValues = slices.Compact(rewardValues)
	one := big.NewInt(1)
	f := big.NewInt(1)
	p := new(big.Int)
	for _, v := range rewardValues {
		mask := p.Sub(p.Lsh(one, uint(v)), one)
		f.Or(f, p.Lsh(p.And(f, mask), uint(v)))
	}
	return f.BitLen() - 1
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach Using Sorting	Time Complexity: O(n log n) due to the use of sorting. Space Complexity: O(1) additional space.
Dynamic Programming with Memoization	Time Complexity: Approx. O(n^2) from evaluating each reward's inclusion/exclusion. Space Complexity: O(n^2) due to the memo dictionary.
Dynamic Programming + Bit Manipulation	–

Complexity analysis

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.

Frequently asked questions

Is Maximum Total Reward Using Operations II easy or hard?

Maximum Total Reward Using Operations II is rated Hard because the naive greedy interpretation fails on edge cases. The correct solution requires recognizing the subset-sum style DP and optimizing it using bit manipulation.

Maximum Total Reward Using Operations II Python/Java solution

Python solutions typically use integers as bitsets or boolean arrays to simulate bit operations. Java and C++ implementations often use BitSet or bitset structures for faster shifting and masking when updating reachable sums.

How to solve Maximum Total Reward Using Operations II in O(n log n)?

Sort the rewards and maintain a bitset representing achievable totals. For each value v, keep only totals smaller than v, shift them by v, and merge with existing states. Bitset operations update multiple sums simultaneously, making the algorithm close to O(n log n) with word-level parallelism.

What is the best approach for Maximum Total Reward Using Operations II?

The most efficient solution uses dynamic programming with a bitset. After sorting the reward values, track reachable reward totals in a bitset and update it by shifting states for each value while keeping only totals smaller than the current reward. This reduces transitions to fast bit operations and handles large inputs efficiently.

Is Maximum Total Reward Using Operations II asked at Google/Amazon/Meta?

Hard dynamic programming and bit manipulation problems similar to this frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests state modeling, subset transitions, and optimization using bitsets or compressed DP.

What data structure is used in Maximum Total Reward Using Operations II?

The optimal solution uses a bitset or boolean DP array to track which reward sums are achievable. Sorting the array and updating states with bit shifts allows efficient subset transitions.

What is the time complexity of Maximum Total Reward Using Operations II?

The optimized bitset dynamic programming solution runs in O(n log n + M / word) time, where n is the number of rewards and M is the maximum possible reward sum tracked by the bitset. Space complexity is O(M) for storing reachable totals.

Maximum Total Reward Using Operations II solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach Using Sorting

Approach 2: Dynamic Programming with Memoization

Approach 3: Dynamic Programming + Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Total Reward Using Operations II solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach Using Sorting

Approach 2: Dynamic Programming with Memoization

Approach 3: Dynamic Programming + Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems