# Maximum Total Reward Using Operations I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-total-reward-using-operations-i)
Canonical: https://scaleengineer.com/dsa/problems/maximum-total-reward-using-operations-i
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**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 <= 2000`
* `1 <= rewardValues[i] <= 2000`

# Approaches
## Top-Down Dynamic Programming (Memoization)
This approach uses recursion with memoization, a technique also known as top-down dynamic programming. The core idea is to explore all possible valid sequences of taking rewards and use a memoization table to store the results of subproblems to avoid redundant computations. A subproblem is defined by the state `(index, currentSum)`, which asks for the maximum reward obtainable considering rewards from `index` onwards, given that the current total reward is `currentSum`.
**Time:** O(N log N + M * V), where `N` is the length of `rewardValues`, `M` is the number of unique rewards, and `V` is the maximum reward value. Sorting takes `O(N log N)`. The DP part involves filling an `M * V` table, with each state computation taking O(1) time. · **Space:** O(M * V), where `M` is the number of unique rewards and `V` is the maximum reward value. This is for the memoization table. The recursion stack adds an additional `O(M)` space.
**Pros:** Relatively straightforward to implement as it directly follows the recursive structure of the problem.; Guaranteed to find the optimal solution.
**Cons:** Higher space complexity compared to bottom-up approaches due to the 2D memoization table.; Can lead to stack overflow for very deep recursion, although not an issue with the given constraints.
### Explanation
First, we preprocess the input `rewardValues` by removing duplicates and sorting them in ascending order. This simplifies the logic, as we only need to consider each unique reward value once, and the sorted order helps in structuring the recursive calls.

The recursive function `solve(index, currentSum)` represents the maximum reward we can get. For each reward at `rewards[index]`, we have two choices: either we skip it and move to the next reward, or we take it. The 'take' option is only available if the reward's value is strictly greater than our `currentSum`. We compute the outcome of both choices and take the maximum. To prevent re-calculating the same state, we use a 2D array `memo` where `memo[index][currentSum]` stores the result for that state. The maximum possible sum is bounded by `2 * max(rewardValues)`, which keeps the size of the memoization table manageable.

```java
import java.util.*;

class Solution {
    private int[][] memo;
    private List<Integer> rewards;
    private int maxSum;

    public int maxTotalReward(int[] rewardValues) {
        Set<Integer> uniqueRewards = new HashSet<>();
        int maxVal = 0;
        for (int val : rewardValues) {
            uniqueRewards.add(val);
            maxVal = Math.max(maxVal, val);
        }
        rewards = new ArrayList<>(uniqueRewards);
        Collections.sort(rewards);

        maxSum = 2 * maxVal;
        memo = new int[rewards.size()][maxSum];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        return solve(0, 0);
    }

    private int solve(int index, int currentSum) {
        if (index == rewards.size()) {
            return currentSum;
        }
        if (memo[index][currentSum] != -1) {
            return memo[index][currentSum];
        }

        // Option 1: Skip the current reward
        int maxReward = solve(index + 1, currentSum);

        // Option 2: Take the current reward if possible
        int currentRewardValue = rewards.get(index);
        if (currentRewardValue > currentSum) {
            if (currentSum + currentRewardValue < maxSum) {
                maxReward = Math.max(maxReward, solve(index + 1, currentSum + currentRewardValue));
            } else {
                 maxReward = Math.max(maxReward, currentSum + currentRewardValue);
            }
        }

        return memo[index][currentSum] = maxReward;
    }
}
```
### Algorithm
1. **Preprocessing**: Remove duplicate reward values and sort them in ascending order. Let's call this array `rewards` of size `M`.
2. **Memoization Table**: Create a 2D memoization table, `memo[index][currentSum]`, to store the results of subproblems. Initialize it with a sentinel value (e.g., -1) to indicate that a state has not been computed.
3. **Recursive Function**: Define a function `solve(index, currentSum)` that computes the maximum reward achievable from `rewards[index...]` given a `currentSum`.
4. **Base Case**: If `index` equals `M`, we have considered all unique rewards, so we return the `currentSum`.
5. **Memoization Check**: If `memo[index][currentSum]` is not the sentinel value, it means we have already solved this subproblem. Return the stored value.
6. **Recursive Step**: At `rewards[index]`, we explore two choices:
    a. **Skip `rewards[index]`**: Recursively call `solve(index + 1, currentSum)`.
    b. **Take `rewards[index]`**: This choice is valid only if `rewards[index] > currentSum`. If so, recursively call `solve(index + 1, currentSum + rewards[index])`.
7. **Combine Results**: The result for the state `(index, currentSum)` is the maximum value returned from the valid choices made in the previous step.
8. **Store and Return**: Store the computed maximum value in `memo[index][currentSum]` before returning it.
9. **Initial Call**: The final answer is obtained by calling `solve(0, 0)`.

## Bottom-Up Dynamic Programming with Boolean Array
A more space-efficient way to solve this problem is using bottom-up dynamic programming. Instead of tracking the maximum reward from a certain state, we track all possible reward sums that can be achieved. We use a boolean array, `possible`, where `possible[x]` is true if a total reward of `x` is achievable. We start with only a sum of 0 being possible. Then, we iterate through each unique reward and update the set of achievable sums.
**Time:** O(N log N + M * V), where `N` is the length of `rewardValues`, `M` is the number of unique rewards, and `V` is the maximum reward value. Sorting takes `O(N log N)`. The nested loops' complexity is `sum(r for r in unique_rewards)`, which is bounded by `O(M * V)`. · **Space:** O(V), where `V` is the maximum reward value. This is for the `possible` boolean array.
**Pros:** More space-efficient than the top-down DP approach.; Typically faster in practice due to better memory locality and no recursion overhead.; The logic is clean and directly builds the set of solutions.
**Cons:** The time complexity is dependent on the values of the rewards, which can be inefficient if reward values are very large (though not an issue with the given constraints).
### Explanation
The process begins by cleaning the input: we take only the unique values from `rewardValues` and sort them. This gives us a candidate list of rewards to pick from. We then set up a boolean DP array, `possible`, where the index represents a potential total reward. `possible[0]` is set to `true` because we start with a total reward of 0.

We then process each unique reward `r` one by one. For each `r`, we check all the sums `x` that we have already marked as possible. If a sum `x` is possible and `r > x`, we can form a new achievable sum `x + r`. We then mark `possible[x + r]` as `true`. A key detail is to iterate through the sums `x` in a way that prevents using a sum generated in the current step. Iterating `x` from `r-1` down to `0` elegantly solves this, as any new sum `x+r` will be at an index greater than `r`, while we are only reading from indices less than `r`.

After processing all unique rewards, the final answer is the largest index in the `possible` array that is marked `true`.

```java
import java.util.*;

class Solution {
    public int maxTotalReward(int[] rewardValues) {
        Set<Integer> uniqueRewardsSet = new HashSet<>();
        int maxVal = 0;
        for (int val : rewardValues) {
            uniqueRewardsSet.add(val);
            maxVal = Math.max(maxVal, val);
        }
        List<Integer> uniqueRewards = new ArrayList<>(uniqueRewardsSet);
        Collections.sort(uniqueRewards);

        int limit = 2 * maxVal;

        boolean[] possible = new boolean[limit + 1];
        possible[0] = true;

        for (int r : uniqueRewards) {
            for (int x = r - 1; x >= 0; x--) {
                if (possible[x]) {
                    if (x + r <= limit) {
                        possible[x + r] = true;
                    }
                }
            }
        }

        for (int i = limit; i >= 0; i--) {
            if (possible[i]) {
                return i;
            }
        }
        return 0;
    }
}
```
### Algorithm
1. **Preprocessing**: Create a sorted list of unique rewards from `rewardValues`, let's call it `unique_rewards`.
2. **DP Array Initialization**: Determine a safe upper bound for the total reward, which is `2 * max(rewardValues)`. Let this be `limit`. Create a boolean array `possible` of size `limit + 1`. Initialize `possible[0] = true` and all other elements to `false`.
3. **Iterate and Update**: Iterate through each reward `r` in `unique_rewards`.
4. **Inner Loop**: For each `r`, iterate through the possible sums `x` from `r - 1` down to `0`. The backward iteration is crucial to ensure that we only use sums that were achievable *before* considering the current reward `r`.
5. **Update `possible` array**: If `possible[x]` is true, it means a sum of `x` is achievable. Since `r > x`, we can now achieve a new sum `x + r`. We mark this new sum as achievable by setting `possible[x + r] = true`.
6. **Find Maximum Reward**: After iterating through all unique rewards, the `possible` array contains all achievable sums. The answer is the largest index `i` for which `possible[i]` is true. This can be found by iterating backwards from `limit`.

## Optimized Bottom-Up DP with BitSet
This approach is a direct optimization of the bottom-up DP with a boolean array. By replacing the `boolean[]` with a `java.util.BitSet`, we can achieve significant improvements in both space and time. A `BitSet` is a vector of bits that grows as needed, making it much more memory-efficient. Furthermore, operations on `BitSet` can be much faster as they can manipulate 64 bits (the size of a `long`) at a time.
**Time:** O(N log N + M * V). While the worst-case bound is similar to the boolean array approach, the use of `nextSetBit` can make it faster in practice by skipping non-achievable sums. A low-level implementation of the shift operation could further reduce the DP part's complexity to `O(N log N + M * V / W)`. · **Space:** O(V / W), where `V` is the maximum reward value and `W` is the word size of the machine (e.g., 64).
**Pros:** Most space-efficient approach, using approximately 8 times less memory than a boolean array.; Potentially the fastest approach, especially if the shift operation is implemented efficiently, as bitwise operations are highly optimized at the hardware level.
**Cons:** The implementation can be slightly more complex than the boolean array version, especially if optimizing the shift operation.; For small-scale problems, the overhead of `BitSet` object creation might make it slightly slower than a simple boolean array.
### Explanation
The fundamental logic is identical to the boolean array approach: we are building the set of all achievable reward sums. However, we leverage the `BitSet` data structure for a more compact representation and potentially faster operations.

The `possible` `BitSet` has a bit set at index `i` if a sum of `i` is achievable. For each reward `r`, the operation of generating new sums `x + r` from existing sums `x < r` corresponds to a bitwise operation. Specifically, we take the bitmask of `possible` for indices `0` to `r-1`, shift this mask to the left by `r` positions, and then OR it with the original `possible` `BitSet`.

While `BitSet` in Java doesn't provide a native `shiftLeft` operation, we can simulate it. A simple simulation involves iterating through the set bits of the partial `BitSet` and setting the shifted bits in a new one. A more advanced (and faster) method would involve manipulating the `BitSet`'s internal `long[]` representation directly. After processing all rewards, the answer is the highest index with a set bit.

```java
import java.util.*;
import java.util.BitSet;

class Solution {
    public int maxTotalReward(int[] rewardValues) {
        Set<Integer> uniqueRewardsSet = new HashSet<>();
        int maxVal = 0;
        for (int val : rewardValues) {
            uniqueRewardsSet.add(val);
            maxVal = Math.max(val, maxVal);
        }
        List<Integer> uniqueRewards = new ArrayList<>(uniqueRewardsSet);
        Collections.sort(uniqueRewards);

        int limit = 2 * maxVal;
        BitSet possible = new BitSet(limit + 1);
        possible.set(0);

        for (int r : uniqueRewards) {
            BitSet head = possible.get(0, r);
            
            // Simulate left shift by r
            BitSet shiftedHead = new BitSet(limit + 1);
            for (int i = head.nextSetBit(0); i >= 0; i = head.nextSetBit(i + 1)) {
                if (i + r <= limit) {
                    shiftedHead.set(i + r);
                }
            }
            
            possible.or(shiftedHead);
        }

        return possible.previousSetBit(limit);
    }
}
```
### Algorithm
1. **Preprocessing**: Same as the previous approach, get a sorted list of unique rewards.
2. **BitSet Initialization**: Determine the `limit` (`2 * max(rewardValues)`). Create a `java.util.BitSet` named `possible` of size `limit + 1`. Set the 0th bit to true: `possible.set(0)`.
3. **Iterate and Update**: For each reward `r` in the unique sorted list:
    a. Get a `BitSet` representing the achievable sums smaller than `r`. This can be done with `possible.get(0, r)`.
    b. Left-shift this temporary `BitSet` by `r` positions. Since `BitSet` lacks a native shift operation, this can be simulated by iterating through its set bits (`nextSetBit`) and setting the corresponding `bit + r` in a new `BitSet`.
    c. Perform a bitwise OR operation between the main `possible` `BitSet` and the new `shifted` `BitSet` to incorporate the newly achievable sums.
4. **Find Maximum Reward**: The result is the index of the highest set bit in the final `possible` `BitSet`. This can be found efficiently using `possible.previousSetBit(limit)`.

# Solutions
### Java

```java
class Solution {
private
  int[] nums;
private
  Integer[] f;
public
  int maxTotalReward(int[] rewardValues) {
    nums = rewardValues;
    Arrays.sort(nums);
    int n = nums.length;
    f = new Integer[nums[n - 1] << 1];
    return dfs(0);
  }
private
  int dfs(int x) {
    if (f[x] != null) {
      return f[x];
    }
    int i = Arrays.binarySearch(nums, x + 1);
    i = i < 0 ? -i - 1 : i;
    int ans = 0;
    for (; i < nums.length; ++i) {
      ans = Math.max(ans, nums[i] + dfs(x + nums[i]));
    }
    return f[x] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxTotalReward(vector<int> &rewardValues) {
    sort(rewardValues.begin(), rewardValues.end());
    int n = rewardValues.size();
    int f[rewardValues.back() << 1];
    memset(f, -1, sizeof(f));
    function<int(int)> dfs = [&](int x) {
      if (f[x] != -1) {
        return f[x];
      }
      auto it = upper_bound(rewardValues.begin(), rewardValues.end(), x);
      int ans = 0;
      for (; it != rewardValues.end(); ++it) {
        ans = max(ans, rewardValues[it - rewardValues.begin()] + dfs(x + *it));
      }
      return f[x] = ans;
    };
    return dfs(0);
  }
};

```

### Python

```python
class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int: @ cache def dfs(x: int) -> int: i = bisect_right(rewardValues, x) ans = 0 for v in rewardValues[i:]: ans = max(ans, v + dfs(x + v)) return ans rewardValues . sort() return dfs(0)

```