Maximum number of operations with the same score ii

Array Dynamic Programming Memoization

34.1% acceptance

Feb 25, 2026

187

Given an array of integers called nums, you can perform any of the following operation while nums contains at least 2 elements: Choose the first two elements of nums and delete them. Choose the last two elements of nums and delete them. Choose the first and the last elements of nums and delete them. The score of the operation is the sum of the deleted elements. Your task is to find the maximum number of operations that can be performed, such that all operations have the same score. Return the maximum number of operations possible that satisfy the condition mentioned above.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_operations(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let s1 = nums[0] + nums[1];
    let s2 = nums[n-2] + nums[n-1];
    let s3 = nums[0] + nums[n-1];
    [s1, s2, s3].iter().map(|&target| Self::count(&nums, target)).max().unwrap()
  }

  fn count(nums: &[i32], target: i32) -> i32 {
    let n = nums.len();
    let mut memo = vec![vec![-1i32; n]; n];
    Self::dp(nums, 0, n - 1, target, &mut memo)
  }

  fn dp(nums: &[i32], l: usize, r: usize, target: i32, memo: &mut Vec<Vec<i32>>) -> i32 {
    if r < l + 1 || memo[l][r] != -1 { return memo[l][r].max(0); }
    let mut res = 0;
    if l + 1 <= r && nums[l] + nums[l+1] == target {
      res = res.max(1 + if l + 2 <= r { Self::dp(nums, l+2, r, target, memo) } else { 0 });
    }
    if r >= 1 && r - 1 >= l && nums[r-1] + nums[r] == target {
      res = res.max(1 + if r >= 2 && l <= r-2 { Self::dp(nums, l, r-2, target, memo) } else { 0 });
    }
    if l <= r && nums[l] + nums[r] == target {
      res = res.max(1 + if l + 1 <= r.saturating_sub(1) { Self::dp(nums, l+1, r-1, target, memo) } else { 0 });
    }
    memo[l][r] = res;
    res
  }
}