LeetCode 3181 - Maximum Total Reward Using Operations II

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation

Solution

Problem Understanding

The problem gives us an array rewardValues, where each element represents a reward we may choose exactly once. We begin with a total reward x = 0, and we are allowed to repeatedly pick an unmarked element only if its value is strictly greater than the current total reward.

Once we choose a reward:

We add its value to x
That index becomes marked and cannot be reused

Our goal is to maximize the final value of x.

The key constraint is the condition:

rewardValues[i] > current_total

This condition makes the problem interesting because the order of selection matters. A reward that is usable early may become unusable later if the running total becomes too large.

For example, suppose we have:

[1, 2, 4]

We can take:

1, total becomes 1
2, total becomes 3
4, total becomes 7

But if we took 4 first:

4, total becomes 4

then neither 1 nor 2 can be taken afterward.

The input size is large:

n <= 5 * 10^4
rewardValues[i] <= 5 * 10^4

This immediately rules out exponential search or naive subset enumeration.

An important observation is that the total reachable reward is actually bounded. Since every chosen number must be larger than the current sum, the running total grows very quickly. This allows a bitset dynamic programming optimization.

Several edge cases are important:

Duplicate values, because taking one copy may prevent taking another
Arrays containing many small numbers
Arrays where a large number should be delayed until later
Arrays with only one element
Already sorted or reverse sorted arrays
Cases where greedily taking the largest value first fails

The problem guarantees:

All values are positive integers
Every element is at least 1
The array is non-empty

These guarantees simplify the DP because we never deal with negative sums or zero-value rewards.

Approaches

Brute Force Approach

A brute-force solution would try every possible sequence of valid picks.

At each step:

We examine every unused reward
If the reward is greater than the current total, we recursively choose it
We continue exploring all valid future paths

This guarantees correctness because every possible valid ordering is explored.

However, the number of states grows exponentially. In the worst case, many rewards remain valid at every step, producing an enormous search tree.

Even memoization is difficult because the state depends on:

Which elements have been used
The current accumulated reward

With up to 5 * 10^4 elements, this is completely infeasible.

Key Insight

The critical observation is that we only care about which total rewards are reachable.

Suppose we currently can achieve some total s.

If we encounter a reward v, we may extend the state only when:

s < v

because the problem requires the chosen reward to be strictly larger than the current total.

If we process rewards in sorted order, we can maintain a bitset DP:

dp[s] = 1 means total s is reachable
For each reward v, every reachable sum s < v can transition to s + v

The bitset allows extremely fast state transitions using bit operations.

The maximum possible reachable sum is manageable because the growth condition forces totals to increase rapidly.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n) or worse	O(2^n)	Explores all valid sequences
Optimal Bitset DP	O(n * M / word_size)	O(M)	Uses bitset transitions for reachable sums

Here, M is the maximum reachable sum, which is bounded by approximately 100000.

Algorithm Walkthrough

Step 1: Sort the Rewards

We first sort the array in ascending order.

Sorting ensures that when processing a reward v, all smaller rewards have already been considered. This creates a clean DP progression and prevents duplicate work.

rewardValues.sort()

Step 2: Initialize the Bitset DP

We maintain a bitset where bit i represents whether total reward i is reachable.

Initially:

Only sum 0 is reachable

So:

dp = 1

because the least significant bit corresponds to sum 0.

Step 3: Process Each Reward

For each reward v:

We want all currently reachable sums s such that s < v
Those sums can transition to s + v

We isolate reachable sums below v using a mask.

mask = (1 << v) - 1
valid = dp & mask

Now valid contains exactly the reachable sums less than v.

Step 4: Shift to Create New Reachable Sums

If sum s is reachable, then s + v becomes reachable.

A left shift by v performs this transition for all sums simultaneously.

dp |= valid << v

This is the key optimization.

Instead of iterating through all sums individually, bit operations update many states in parallel.

Step 5: Find the Maximum Reachable Sum

After processing all rewards, the answer is the largest set bit in dp.

We can obtain it using:

dp.bit_length() - 1

because the highest set bit corresponds to the maximum reachable sum.

Why it works

The DP invariant is:

dp[s] = reachable total reward s

Initially, only 0 is reachable.

For each reward v, the problem allows us to append v only to totals smaller than v. By masking with (1 << v) - 1, we consider exactly those valid states.

The left shift generates all new reachable totals s + v.

Since every valid transition defined by the problem is included exactly once, the DP explores all achievable totals. Therefore, the maximum reachable sum stored in the bitset is the optimal answer.

Python Solution

from typing import List

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues.sort()

        dp = 1

        for value in rewardValues:
            valid_sums = dp & ((1 << value) - 1)
            dp |= valid_sums << value

        return dp.bit_length() - 1

The implementation begins by sorting the rewards so that smaller values are processed first. This guarantees that when handling a value value, all previously reachable sums are already finalized.

The variable dp acts as a compact bitset. Bit i is set if total reward i can be achieved.

For each reward:

valid_sums = dp & ((1 << value) - 1)

extracts all reachable sums strictly smaller than value.

Then:

dp |= valid_sums << value

creates all new totals formed by adding value.

Finally:

dp.bit_length() - 1

returns the highest reachable sum.

The solution is extremely efficient because Python integers internally support arbitrary-length bit operations implemented in optimized C code.

Go Solution

package main

import (
	"math/big"
	"sort"
)

func maxTotalReward(rewardValues []int) int {
	sort.Ints(rewardValues)

	dp := big.NewInt(1)

	for _, value := range rewardValues {
		mask := new(big.Int).Lsh(big.NewInt(1), uint(value))
		mask.Sub(mask, big.NewInt(1))

		valid := new(big.Int).And(dp, mask)
		shifted := new(big.Int).Lsh(valid, uint(value))

		dp.Or(dp, shifted)
	}

	return dp.BitLen() - 1
}

The Go solution uses math/big.Int because Go integers have fixed size and cannot act as arbitrarily large bitsets like Python integers.

Key implementation details:

sort.Ints sorts the array in ascending order
big.Int supports arbitrary-precision bit manipulation
Lsh performs left shifts
And applies the mask
BitLen() - 1 finds the highest reachable sum

Unlike Python, Go requires explicit allocation of intermediate big.Int objects because most operations mutate the receiver.

Worked Examples

Example 1

Input:

rewardValues = [1,1,3,3]

Sorted array:

[1,1,3,3]

Initial state:

dp = 1
reachable sums = {0}

Step	Value	Reachable Before	Valid Sums (< value)	New Sums	Reachable After
1	1	{0}	{0}	{1}	{0,1}
2	1	{0,1}	{0}	{1}	{0,1}
3	3	{0,1}	{0,1}	{3,4}	{0,1,3,4}
4	3	{0,1,3,4}	{0,1}	{3,4}	{0,1,3,4}

Maximum reachable sum:

Example 2

Input:

rewardValues = [1,6,4,3,2]

Sorted array:

[1,2,3,4,6]

Initial reachable sums:

{0}

Step	Value	Reachable Before	Valid Sums	New Sums	Reachable After
1	1	{0}	{0}	{1}	{0,1}
2	2	{0,1}	{0,1}	{2,3}	{0,1,2,3}
3	3	{0,1,2,3}	{0,1,2}	{3,4,5}	{0,1,2,3,4,5}
4	4	{0,1,2,3,4,5}	{0,1,2,3}	{4,5,6,7}	{0,1,2,3,4,5,6,7}
5	6	{0,1,2,3,4,5,6,7}	{0,1,2,3,4,5}	{6,7,8,9,10,11}	{0,1,2,3,4,5,6,7,8,9,10,11}

Maximum reachable sum:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * M / word_size)	Bitset operations process many states simultaneously
Space	O(M)	The bitset stores reachable sums

Here, M is the maximum reachable reward sum.

Although the theoretical maximum sum could be large, the strict growth condition significantly limits reachable states. In practice, the bitset remains efficient for the given constraints.

Python's arbitrary-length integers and Go's big.Int both internally store data in machine-word chunks, allowing bulk bitwise operations to run very quickly.

Test Cases

sol = Solution()

assert sol.maxTotalReward([1, 1, 3, 3]) == 4  # example 1
assert sol.maxTotalReward([1, 6, 4, 3, 2]) == 11  # example 2

assert sol.maxTotalReward([1]) == 1  # single element
assert sol.maxTotalReward([2]) == 2  # single larger value

assert sol.maxTotalReward([1, 2, 4, 8]) == 15  # perfect doubling chain
assert sol.maxTotalReward([1, 1, 1, 1]) == 1  # duplicates cannot chain

assert sol.maxTotalReward([1, 2, 3]) == 5  # choose 2 then 3
assert sol.maxTotalReward([1, 2, 10]) == 13  # accumulate before large value

assert sol.maxTotalReward([5, 1, 2]) == 8  # sorting required
assert sol.maxTotalReward([3, 3, 3]) == 3  # only one usable

assert sol.maxTotalReward([1, 3, 6, 13]) == 23  # chain all rewards
assert sol.maxTotalReward([1, 4, 9, 16]) == 30  # sparse growth

assert sol.maxTotalReward([2, 4, 8, 16]) == 30  # start directly with 2
assert sol.maxTotalReward([1, 50_000]) == 50_001  # large value edge case

Test Case Summary

Test	Why
`[1,1,3,3]`	Verifies duplicate handling
`[1,6,4,3,2]`	Validates general DP transitions
`[1]`	Smallest valid input
`[2]`	Single non-one value
`[1,2,4,8]`	Full chaining behavior
`[1,1,1,1]`	Duplicate values cannot repeatedly apply
`[1,2,3]`	Greedy ordering matters
`[1,2,10]`	Large value after accumulation
`[5,1,2]`	Confirms sorting is necessary
`[3,3,3]`	Only one identical value usable
`[1,3,6,13]`	Longer valid chain
`[1,4,9,16]`	Sparse increasing rewards
`[2,4,8,16]`	Starting from non-one value
`[1,50000]`	Upper-value boundary

Edge Cases

One important edge case is arrays containing many duplicate values. For example:

[1,1,1,1]

After taking the first 1, the total becomes 1, meaning no other 1 can be chosen because the condition requires strictly greater values. A naive implementation might accidentally allow repeated equal values. The bitmask condition:

valid_sums = dp & ((1 << value) - 1)

correctly excludes sums equal to value.

Another important edge case is unsorted input. Consider:

[5,1,2]

If processed in original order, taking 5 first prevents taking smaller values later. The optimal strategy is actually 1 -> 2 -> 5. Sorting guarantees the DP considers transitions in the correct progression and does not miss optimal constructions.

A third important edge case is extremely large values near the constraint boundary. For example:

[1, 50000]

The implementation must efficiently handle large shifts and large reachable sums. Using bitsets avoids allocating enormous DP tables of booleans and keeps operations compact and efficient even for large values.

A fourth subtle edge case is when skipping a smaller value leads to a better future chain. Greedy approaches often fail here. For example:

[1,2,3]

Taking 1 then 2 produces total 3, which prevents taking 3. The optimal choice is 2 -> 3 = 5. The DP correctly explores all reachable sums simultaneously, so it never commits prematurely to a single greedy path.