Maximum subarray sum after one operation

Array Dynamic Programming

65.2% acceptance

Mar 31, 2026

312

You are given an integer array nums. You must perform exactly one operation where you can replace one element nums[i] with nums[i] * nums[i]. Return the maximum possible subarray sum after exactly one operation. The subarray must be non-empty.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum_after_operation(nums: Vec<i32>) -> i32 {
    // dp_no: max subarray sum ending here with no squaring done
    // dp_sq: max subarray sum ending here with exactly one squaring done
    let mut dp_no = nums[0] as i64;
    let mut dp_sq = (nums[0] as i64) * (nums[0] as i64);
    let mut ans = dp_sq;

    for i in 1..nums.len() {
      let x = nums[i] as i64;
      let new_sq = (dp_no + x * x).max(dp_sq + x).max(x * x);
      let new_no = (dp_no + x).max(x);
      dp_sq = new_sq;
      dp_no = new_no;
      ans = ans.max(dp_sq);
    }
    ans as i32
  }
}