# Maximum Total Reward Using Operations II
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-total-reward-using-operations-ii)
Canonical: https://scaleengineer.com/dsa/problems/maximum-total-reward-using-operations-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Mitsogo](https://scaleengineer.com/companies/mitsogo)
---
## 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 * 104`
* `1 <= rewardValues[i] <= 5 * 104`

# Approaches
## Dynamic Programming with Boolean Array
This approach uses dynamic programming to determine all possible reward sums that can be achieved. The core idea is based on the observation that if a set of rewards is collectible, it is always possible to collect them in increasing order of their value. This simplifies the problem significantly, as we can process the rewards one by one after sorting them.

We maintain a boolean array, `possible`, where `possible[x]` is `true` if a total reward of `x` is achievable. The maximum size of this array is bounded by `2 * max(rewardValues)`, which is a key insight to make the state space of the DP manageable in terms of memory.
**Time:** O(N log N + U * V_max), where `N` is the number of rewards, `U` is the number of unique rewards, and `V_max` is the maximum reward value. Sorting takes `O(N log N)`. The nested loops can take up to `O(U * V_max)` time in the worst case, which is too slow for the given constraints. · **Space:** O(V_max), where `V_max` is the maximum value in `rewardValues`. This is for the `possible` boolean array.
**Pros:** Conceptually straightforward and easier to implement compared to more optimized solutions.; Correctly solves the problem for smaller constraints.
**Cons:** The time complexity is too high for the given constraints, leading to a 'Time Limit Exceeded' error on larger test cases.
### Explanation
```java
import java.util.Arrays;

class Solution {
    public int maxTotalReward(int[] rewardValues) {
        Arrays.sort(rewardValues);
        
        // Remove duplicates as processing the same value multiple times is redundant for this logic
        int n = rewardValues.length;
        int[] uniqueRewards = new int[n];
        int uSize = 0;
        if (n > 0) {
            uniqueRewards[uSize++] = rewardValues[0];
            for (int i = 1; i < n; i++) {
                if (rewardValues[i] != rewardValues[i-1]) {
                    uniqueRewards[uSize++] = rewardValues[i];
                }
            }
        }

        int maxVal = uSize > 0 ? uniqueRewards[uSize - 1] : 0;
        if (maxVal == 0) return 0;
        
        boolean[] possible = new boolean[2 * maxVal];
        possible[0] = true;
        
        int highestPossible = 0;

        for (int i = 0; i < uSize; i++) {
            int r = uniqueRewards[i];
            // Iterate downwards to avoid using the current reward `r` multiple times in this step.
            // We only need to check sums up to `r-1`.
            for (int x = Math.min(highestPossible, r - 1); x >= 0; x--) {
                if (possible[x]) {
                    if (x + r < 2 * maxVal) {
                        possible[x + r] = true;
                        highestPossible = Math.max(highestPossible, x + r);
                    }
                }
            }
        }
        
        return highestPossible;
    }
}
```
### Algorithm
*   Sort the `rewardValues` array in non-decreasing order.
*   To handle duplicate reward values correctly and efficiently, create a new array `uniqueRewards` containing only the distinct values from `rewardValues`.
*   Determine the maximum possible sum. If the last reward taken is `r` and the sum before that was `x`, the final sum is `x+r`. The condition `r > x` implies `x+r < 2r`. Thus, the maximum possible total reward is less than `2 * max(rewardValues)`.
*   Initialize a boolean array `possible` of size `2 * max(rewardValues)`. Set `possible[0] = true` to represent the initial state of having a total reward of 0. All other elements are initialized to `false`.
*   Keep track of the highest sum achieved so far, say `highestPossible`, initialized to 0.
*   Iterate through each reward `r` in `uniqueRewards`.
*   For each `r`, iterate through the already possible sums `x` from `highestPossible` down to 0.
*   If `possible[x]` is true and `x < r`, it means we can take the reward `r` to form a new achievable sum `x + r`. Set `possible[x + r] = true` and update `highestPossible = max(highestPossible, x + r)`.
*   The downward iteration for `x` is important to ensure that we only use rewards from previous steps to form new sums with the current reward `r`.
*   After iterating through all unique rewards, the final value of `highestPossible` is the maximum total reward.

## Dynamic Programming with Bitmask Optimization
This approach enhances the dynamic programming solution by using bitmasks for a significant performance boost. The set of achievable sums is represented by a bitmask (e.g., a `long[]` array), where the `i`-th bit is set if a sum of `i` is possible.

The key operation is updating this bitmask. For a given reward `r`, we want to add `r` to all existing achievable sums `x` where `x < r`. In the world of bitmasks, this translates to taking the portion of the `achieved` bitmask representing sums less than `r`, left-shifting it by `r` positions, and then OR-ing it with the original `achieved` bitmask. This bit-level parallelism allows us to update many states simultaneously, drastically reducing the runtime compared to iterating through each sum one by one.
**Time:** O(N log N + sum(unique_rewards) / w). Sorting takes `O(N log N)`. The DP update for each unique reward `r` takes `O(r/w)` time. The total time for all updates is proportional to the sum of all unique reward values, divided by the word size `w`. This is efficient enough for the given constraints. · **Space:** O(V_max / w), where `V_max` is the maximum reward value and `w` is the word size (64 for `long`). This is for the `achieved` bitmask.
**Pros:** Highly efficient and passes the given constraints.; Leverages bit-level parallelism to update multiple DP states in a single operation.
**Cons:** The implementation is more complex due to manual bit manipulation of the `long[]` array.; Requires a good understanding of bitwise operations and how they translate to array manipulations.
### Explanation
```java
import java.util.Arrays;

class Solution {
    public int maxTotalReward(int[] rewardValues) {
        Arrays.sort(rewardValues);
        int n = rewardValues.length;
        
        int[] uniqueRewards = new int[n];
        int uSize = 0;
        if (n > 0) {
            uniqueRewards[uSize++] = rewardValues[0];
            for (int i = 1; i < n; i++) {
                if (rewardValues[i] != rewardValues[i-1]) {
                    uniqueRewards[uSize++] = rewardValues[i];
                }
            }
        }

        int maxVal = uSize > 0 ? uniqueRewards[uSize - 1] : 0;
        if (maxVal == 0) return 0;
        
        int M = 2 * maxVal;
        long[] achieved = new long[M / 64 + 2];
        achieved[0] = 1L; // Sum 0 is achievable

        for (int i = 0; i < uSize; i++) {
            int r = uniqueRewards[i];
            
            // 1. Create a temporary bitmask of achievable sums less than r
            int lastWordIdx = (r - 1) / 64;
            long[] sumsToShift = new long[lastWordIdx + 1];
            System.arraycopy(achieved, 0, sumsToShift, 0, lastWordIdx + 1);
            
            long mask = (1L << (r % 64)) - 1;
            if (r % 64 == 0) mask = -1L; // all 1s for a full word
            sumsToShift[lastWordIdx] &= mask;

            // 2. Shift this temporary bitmask by r and OR it with 'achieved'
            int wordShift = r / 64;
            int bitShift = r % 64;
            
            for (int k = 0; k < sumsToShift.length; k++) {
                if (sumsToShift[k] == 0) continue;
                long val = sumsToShift[k];
                
                if (bitShift == 0) {
                    achieved[k + wordShift] |= val;
                } else {
                    achieved[k + wordShift] |= (val << bitShift);
                    if (k + wordShift + 1 < achieved.length) {
                        achieved[k + wordShift + 1] |= (val >>> (64 - bitShift));
                    }
                }
            }
        }

        // 3. Find the highest achievable sum
        for (int i = M - 1; i >= 0; i--) {
            if ((achieved[i / 64] & (1L << (i % 64))) != 0) {
                return i;
            }
        }
        return 0;
    }
}
```
### Algorithm
*   First, sort the `rewardValues` array and then extract the unique values into a new array, `uniqueRewards`. This is because for any given achievable sum `x`, a reward value `r` can be added at most once, so processing the same `r` multiple times is redundant.
*   The maximum possible sum is less than `2 * V_max`, where `V_max` is the maximum reward value. We create a bitmask, implemented as a `long[]` array named `achieved`, to store the achievable sums. The size of this array will be `(2 * V_max) / 64 + 2`.
*   Initialize the bitmask by setting the bit for sum 0: `achieved[0] = 1L`.
*   Iterate through each unique reward `r` from `uniqueRewards`.
*   For each `r`, we need to perform the operation: `achieved |= (achieved_lt_r << r)`, where `achieved_lt_r` is a bitmask of all achievable sums strictly less than `r`.
*   This operation is implemented by:
    1.  Creating a temporary bitmask (`sumsToShift`) that is a copy of the `achieved` bitmask, but only for bits corresponding to sums less than `r`. This involves copying the first `(r-1)/64` words and masking the last word.
    2.  Shifting this temporary bitmask `sumsToShift` left by `r` positions. This is done by calculating a `wordShift = r / 64` and a `bitShift = r % 64` and applying them to each `long` in `sumsToShift`.
    3.  Performing a bitwise OR of the shifted result back into the main `achieved` bitmask.
*   After iterating through all unique rewards, the final `achieved` bitmask contains all possible sums. The answer is the index of the highest set bit, which can be found by scanning the `long[]` array from the end.

# Solutions
### Java

```java
import java.math.BigInteger ; import java.util.Arrays ; class Solution { public int maxTotalReward ( int [] rewardValues ) { int [] nums = Arrays . stream ( rewardValues ). distinct (). sorted (). toArray (); BigInteger f = BigInteger . ONE ; for ( int v : nums ) { BigInteger mask = BigInteger . ONE . shiftLeft ( v ). subtract ( BigInteger . ONE ); BigInteger shifted = f . and ( mask ). shiftLeft ( v ); f = f . or ( shifted ); } return f . bitLength () - 1 ; } }
```

### CPP

```cpp
class Solution { public: int maxTotalReward ( vector < int >& rewardValues ) { sort ( rewardValues . begin (), rewardValues . end ()); rewardValues . erase ( unique ( rewardValues . begin (), rewardValues . end ()), rewardValues . end ()); bitset < 100000 > f { 1 }; for ( int v : rewardValues ) { int shift = f . size () - v ; f |= f << shift >> ( shift - v ); } for ( int i = rewardValues . back () * 2 - 1 ;; i -- ) { if ( f . test ( i )) { return i ; } } } };
```

### Python

```python
class Solution : def maxTotalReward ( self , rewardValues : List [ int ]) -> int : nums = sorted ( set ( rewardValues )) f = 1 for v in nums : f |= ( f & (( 1 << v ) - 1 )) << v return f . bit_length () - 1
```