Maximum Total Reward Using Operations I

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

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.

1import java.util.*;2 3class Solution {4    private int[][] memo;5    private List<Integer> rewards;6    private int maxSum;7 8    public int maxTotalReward(int[] rewardValues) {9        Set<Integer> uniqueRewards = new HashSet<>();10        int maxVal = 0;11        for (int val : rewardValues) {12            uniqueRewards.add(val);13            maxVal = Math.max(maxVal, val);14        }15        rewards = new ArrayList<>(uniqueRewards);16        Collections.sort(rewards);17 18        maxSum = 2 * maxVal;19        memo = new int[rewards.size()][maxSum];20        for (int[] row : memo) {21            Arrays.fill(row, -1);22        }23 24        return solve(0, 0);25    }26 27    private int solve(int index, int currentSum) {28        if (index == rewards.size()) {29            return currentSum;30        }31        if (memo[index][currentSum] != -1) {32            return memo[index][currentSum];33        }34 35        // Option 1: Skip the current reward36        int maxReward = solve(index + 1, currentSum);37 38        // Option 2: Take the current reward if possible39        int currentRewardValue = rewards.get(index);40        if (currentRewardValue > currentSum) {41            if (currentSum + currentRewardValue < maxSum) {42                maxReward = Math.max(maxReward, solve(index + 1, currentSum + currentRewardValue));43            } else {44                 maxReward = Math.max(maxReward, currentSum + currentRewardValue);45            }46        }47 48        return memo[index][currentSum] = maxReward;49    }50}

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.

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.

1import java.util.*;2 3class Solution {4    public int maxTotalReward(int[] rewardValues) {5        Set<Integer> uniqueRewardsSet = new HashSet<>();6        int maxVal = 0;7        for (int val : rewardValues) {8            uniqueRewardsSet.add(val);9            maxVal = Math.max(maxVal, val);10        }11        List<Integer> uniqueRewards = new ArrayList<>(uniqueRewardsSet);12        Collections.sort(uniqueRewards);13 14        int limit = 2 * maxVal;15 16        boolean[] possible = new boolean[limit + 1];17        possible[0] = true;18 19        for (int r : uniqueRewards) {20            for (int x = r - 1; x >= 0; x--) {21                if (possible[x]) {22                    if (x + r <= limit) {23                        possible[x + r] = true;24                    }25                }26            }27        }28 29        for (int i = limit; i >= 0; i--) {30            if (possible[i]) {31                return i;32            }33        }34        return 0;35    }36}

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

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.

1import java.util.*;2import java.util.BitSet;3 4class Solution {5    public int maxTotalReward(int[] rewardValues) {6        Set<Integer> uniqueRewardsSet = new HashSet<>();7        int maxVal = 0;8        for (int val : rewardValues) {9            uniqueRewardsSet.add(val);10            maxVal = Math.max(val, maxVal);11        }12        List<Integer> uniqueRewards = new ArrayList<>(uniqueRewardsSet);13        Collections.sort(uniqueRewards);14 15        int limit = 2 * maxVal;16        BitSet possible = new BitSet(limit + 1);17        possible.set(0);18 19        for (int r : uniqueRewards) {20            BitSet head = possible.get(0, r);21            22            // Simulate left shift by r23            BitSet shiftedHead = new BitSet(limit + 1);24            for (int i = head.nextSetBit(0); i >= 0; i = head.nextSetBit(i + 1)) {25                if (i + r <= limit) {26                    shiftedHead.set(i + r);27                }28            }29            30            possible.or(shiftedHead);31        }32 33        return possible.previousSetBit(limit);34    }35}