Skip to main content

1911. Maximum Alternating Subsequence Sum

medium

Pick a subsequence whose alternating sum (first + minus second + plus third...) is maximal. Two-state DP — last picked at even or odd position.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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).

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

Examples

Example 1

Input
nums = [4,2,5,3]
Output
7

Explanation: It is optimal to choose the subsequence [4,2,5] with alternating sum (4 + 5) - 2 = 7.

Example 2

Input
nums = [5,6,7,8]
Output
8

Explanation: It is optimal to choose the subsequence [8] with alternating sum 8.

Example 3

Input
nums = [6,2,1,2,4,5]
Output
10

Explanation: It is optimal to choose the subsequence [6,1,5] with alternating sum (6 + 5) - 1 = 10.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two states per index: best sum if the next pick will be at an even position vs odd position.

Hint 2

even = max(even, odd + nums[i]); odd = max(odd, even_prev - nums[i]).

Hint 3

Start with even = 0, odd = 0. Answer = even after the sweep.

Solution approach

Reveal approach

Two-state DP tracking the running maximum alternating sum where the next picked element would go at an even or odd index. Initialize even = 0 (no picks yet — next pick will be at even index 0 and added) and odd = 0. For each num: store prev_even = even; update even = max(even, odd + num) (either skip, or add num as a new even-index element extending an odd-ending subsequence); update odd = max(odd, prev_even - num). Return even. The previous-step snapshot of even is needed to keep odd's update consistent with the same time-slice. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • state-machine

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

More DP 1D practice problems

See all DP 1D problems →