Skip to content

3181. Maximum Total Reward Using Operations II

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  // Same as 3180. Maximum Total Reward Using Operations I
  int maxTotalReward(vector<int>& rewardValues) {
    constexpr int kPossibleRewards = 100'000;
    // dp[num] := true if reward `num` is achievable
    bitset<kPossibleRewards> dp;
    dp[0] = true;

    ranges::sort(rewardValues);

    for (const int num : rewardValues) {
      bitset<kPossibleRewards> newBits = dp;
      // Remove the numbers >= the current number.
      newBits <<= kPossibleRewards - num;
      newBits >>= kPossibleRewards - num;
      dp |= newBits << num;
    }

    for (int ans = kPossibleRewards - 1; ans >= 0; --ans)
      if (dp[ans])
        return ans;

    throw;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import java.math.BigInteger;

class Solution {
  // Same as 3180. Maximum Total Reward Using Operations I
  public int maxTotalReward(int[] rewardValues) {
    BigInteger one = BigInteger.ONE;
    BigInteger dp = one; // the possible rewards (initially, 0 is achievable)

    Arrays.sort(rewardValues);

    for (final int num : rewardValues) {
      // Remove the numbers >= the current number.
      BigInteger maskBitsLessThanNum = one.shiftLeft(num).subtract(one);
      BigInteger bitsLessThanNum = dp.and(maskBitsLessThanNum);
      dp = dp.or(bitsLessThanNum.shiftLeft(num));
    }

    return dp.bitLength() - 1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  # Same as 3180. Maximum Total Reward Using Operations I
  def maxTotalReward(self, rewardValues: list[int]) -> int:
    dp = 1  # the possible rewards (initially, 0 is achievable)

    for num in sorted(rewardValues):
      # Remove the numbers >= the current number.
      smallerNums = dp & ((1 << num) - 1)
      dp |= smallerNums << num

    return dp.bit_length() - 1