Maximum alternating subsequence sum

Array Dynamic Programming

59.0% acceptance

Feb 25, 2026

1428

The alternating sum of a 0-indexed array is defined as the sum of the elements at even indices minus the sum of the elements at odd indices. For example, the alternating sum of [4,2,5,3] is (4 + 5) - (2 + 3) = 4. Given an array nums, return the maximum alternating sum of any subsequence of nums (after reindexing the elements of the subsequence). A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_alternating_sum(nums: Vec<i32>) -> i64 {
    let mut even = 0i64; // max sum when next pick is at even index
    let mut odd = 0i64; // max sum when next pick is at odd index
    for &x in &nums {
      let x = x as i64;
      let new_even = even.max(odd - x);
      let new_odd = odd.max(even + x);
      even = new_even;
      odd = new_odd;
    }
    even.max(odd)
  }
}