Maximum total reward using operations i

Array Dynamic Programming

30.7% acceptance

Feb 24, 2026

212

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 max_total = 2 * max_val;
    let mut dp = vec![false; max_total + 1];
    dp[0] = true;
    for &v in &vals {
      let v = v as usize;
      // For each achievable sum x < v, x+v is now achievable
      for x in (0..v).rev() {
        if dp[x] {
          dp[x + v] = true;
        }
      }
    }
    for i in (0..=max_total).rev() {
      if dp[i] {
        return i as i32;
      }
    }
    0
  }
}