Maximize total cost of alternating subarrays

Array Dynamic Programming

29.5% acceptance

Feb 24, 2026

194

You are given an integer array nums with length n. The cost of a subarray nums[l..r] is defined as: cost(l, r) = nums[l] - nums[l+1] + ... + nums[r] * (-1)^(r-l) Your task is to split nums into subarrays such that the total cost of the subarrays is maximized. Return an integer denoting the maximum total cost of the subarrays after splitting optimally.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_total_cost(nums: Vec<i32>) -> i64 {
    // Within a subarray cost alternates: +,-,+,-,...
    // When we split at index i, the next subarray restarts with +.
    // Key insight: the only way to benefit from splitting is when we can avoid subtracting
    // a positive value at an even position in the current subarray.
    // dp[i] = max total cost using nums[0..i]
    // At position i (0-indexed), within current subarray it may be added (+) or subtracted (-).
    // State: dp_plus[i] = max cost where nums[i] contributes positively (start of new subarray or even offset)
    // dp_minus[i] = max cost where nums[i] contributes negatively
    let n = nums.len();
    let mut dp_plus = nums[0] as i64;
    let mut dp_minus = i64::MIN / 2;
    for i in 1..n {
      let v = nums[i] as i64;
      let new_plus = dp_plus.max(dp_minus) + v; // start new subarray (always +) or continue after - with +
      // Wait: after +, next can be - (continue) or + (start new subarray for next element)
      // After -, next must be + (continue same subarray alternation)
      let new_minus = dp_plus - v; // continue current subarray: was +, now -
      dp_plus = new_plus;
      dp_minus = new_minus;
    }
    dp_plus.max(dp_minus)
  }
}