3181. Maximum Total Reward Using Operations II

Description

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

Solutions

Solution 1: 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] = \text{True}$, and all other values are $\text{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] = \text{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$.

• 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) {
f = f.or(shifted);
}
return f.bitLength() - 1;
}
}

• 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;
}
}
}
};

• 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


• 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 {