# 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]=True, and all other values are 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≤j−v<v. Thus, the state transition equation is:

f[i][j]=f[i−1][j]∨f[i−1][j−v]

The final answer is maxj|f[n][j]=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]∨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×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.

#### Python3

```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
```

#### Java

```java
import java.math.BigInteger;

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

#### C++

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

#### Go

```go
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 {
        mask := p.Sub(p.Lsh(one, uint(v)), one)
        f.Or(f, p.Lsh(p.And(f, mask), uint(v)))
    }
    return f.BitLen() - 1
}
```

#### TypeScript

```typescript
function maxTotalReward(rewardValues: number[]): number {
    rewardValues.sort((a, b) => a - b);
    rewardValues = [...new Set(rewardValues)];
    let f = 1n;
    for (const x of rewardValues) {
        const mask = (1n << BigInt(x)) - 1n;
        f = f | ((f & mask) << BigInt(x));
    }
    return f.toString(2).length - 1;
}
```