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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Maximum Alternating Subsequence Sum and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →