Maximum total reward using operations ii

Array Dynamic Programming Bit Manipulation

21.9% acceptance

Feb 24, 2026

133

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 and mark the index i. Return an integer denoting the maximum total reward you can collect.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_total_reward(reward_values: Vec<i32>) -> i32 {
    let mut vals = reward_values.clone();
    vals.sort_unstable();
    vals.dedup();
    let max_val = *vals.last().unwrap() as usize;
    let total_bits = 2 * max_val + 1;
    let n_words = (total_bits + 63) / 64;
    let mut dp = vec![0u64; n_words];
    dp[0] = 1; // bit 0 = sum 0 is achievable

    for &v in &vals {
      let v = v as usize;
      // Need to add: for each set bit position x < v, set bit x+v
      // Equivalent to: dp |= (dp & mask_lt_v) << v
      // mask_lt_v: bits 0..v-1 are set
      let word_v = v / 64;
      let bit_v = v % 64;

      // Build masked copy (only bits < v)
      let mut masked = dp.clone();
      if word_v < n_words {
        // Clear bit v and above in word word_v
        if bit_v > 0 {
          masked[word_v] &= (1u64 << bit_v) - 1;
        } else {
          masked[word_v] = 0;
        }
        for w in (word_v + 1)..n_words {
          masked[w] = 0;
        }
      }

      // Shift masked left by v bits and OR into dp
      for i in (0..n_words).rev() {
        let src_word = if i >= word_v { i - word_v } else { continue };
        let new_bits = if bit_v == 0 {
          masked[src_word]
        } else {
          let high = masked[src_word] << bit_v;
          let low = if src_word > 0 { masked[src_word - 1] >> (64 - bit_v) } else { 0 };
          high | low
        };
        dp[i] |= new_bits;
      }
      // Handle the shift for word boundary (the low part of the first shifted word)
      if bit_v > 0 && word_v < n_words {
        // word_v-th destination word gets the low part from masked[0] (if word_v == 0 handled above)
        // Actually already handled in the loop above when i = word_v and src_word = 0
      }
    }

    // Find highest set bit
    for w in (0..n_words).rev() {
      if dp[w] != 0 {
        return (w * 64 + 63 - dp[w].leading_zeros() as usize) as i32;
      }
    }
    0
  }
}