Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximum Alternating Subsequence Sum solution and explanation

MediumArrayDynamic Programming5 min read59.4% acceptanceUpdated 9 Apr 2026
Asked atQuinceGoogleMetaBloomberg
Practise Maximum Alternating Subsequence Sum
26:44
Maximum Alternating Subsequence Sum |Recursion & Memo|Tree Diagram|DP Concepts & Qns-9|Leetcode-1911codestorywithMIK · 26:44 · 35K viewsWatch on YouTube
9 more videos on this problem
  1. Maximum Alternating Subsequence Sum |Recursion & Memo|Tree Diagram|DP Concepts & Qns-9|Leetcode-1911codestorywithMIK · 26:44 · 35K views
  2. Maximum Alternating Subsequence Sum - Dynamic Programming - Leetcode 1911 - PythonNeetCode · 13:23 · 32K views
  3. Maximum Alternating Subsequence Sum | BOTTOM UP | INTUITION | DP Concepts & Qns - 10 | Leetcode-1911codestorywithMIK · 25:58 · 19K views
  4. Leetcode solution 5782. Maximum Alternating Subsequence SumFraz · 18:26 · 7K views
  5. Maximum Alternating Subsequence Sum || LeetcodePepcoding · 32:29 · 4K views
  6. LeetCode 1911. Maximum Alternating Subsequence SumHappy Coding · 12:49 · 1K views
  7. Leetcode Maximum Alternating Subsequence Sum | Biweekly Contest 55Sandip Jana · 18:32 · 832 views
  8. 1911. Maximum Alternating Subsequence Sum (Leetcode Medium)Programming Live with Larry · 10:14 · 772 views
  9. LeetCode 1911. Maximum Alternating Subsequence Sum | C++ | in HindiNitesh Kumar · 17:38 · 683 views
  10. MAXIMUM ALTERNATING SUBSEQUENCE SUM | LEETCODE 1911 | 2D DP | DP CONCEPTS |proteinCoder · 11:05 · 135 views

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

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.

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.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Approach overview

Problem Overview: You are given an integer array and must choose a subsequence whose alternating sum is maximized. The alternating sum means elements are added and subtracted in order: a0 - a1 + a2 - a3 .... The subsequence can skip any elements but must keep the original order. The challenge is deciding which numbers to include so the positive positions carry large values while negative positions carry smaller ones.

Approach 1: Dynamic Programming (O(n) time, O(1) space)

This problem maps naturally to dynamic programming. While scanning the array, track two states: the best alternating sum when the next operation is addition (even index in the subsequence) and the best sum when the next operation is subtraction (odd). For each number x, you either include it or skip it. Including it transitions between states: adding x updates the even state, subtracting x updates the odd state.

The recurrence is straightforward: update the "add" state using the previous subtract state plus the current value, and update the "subtract" state using the previous add state minus the value. Because only the previous states matter, you store just two variables instead of a full DP table. This reduces space complexity to O(1) while keeping time complexity O(n).

Approach 2: Greedy with Two Accumulators (O(n) time, O(1) space)

A greedy interpretation leads to an even simpler implementation. Maintain two accumulators: add for the best sum when the next operation is addition and subtract for the best sum when the next operation is subtraction. Iterate through the array once. For each value, compute the best new states by either taking the element or skipping it.

The key insight: if a value improves the alternating pattern, include it immediately. Updating the accumulators effectively captures the same transitions as the DP solution but framed as a greedy decision process. Since each element is processed exactly once and only constant variables are used, the algorithm runs in O(n) time with O(1) space.

This approach is often easier to reason about because the two accumulators represent the best possible sums for even and odd positions in the subsequence. The logic mirrors classic stock-trading style DP problems where you alternate between "buy" and "sell" states.

Recommended for interviews: The greedy two-accumulator version is what most interviewers expect. It demonstrates strong understanding of state transitions and optimization from dynamic programming to constant-space logic. Explaining the DP formulation first shows you understand the state definition, while deriving the greedy version highlights optimization skills.

Approach 1: Dynamic Programming Approach

In this approach, we use dynamic programming to keep track of the maximum alternating sum at each step. We maintain two variables to track the maximum sum of subsequences when the last index used was even ('even_idx_sum') and odd ('odd_idx_sum'). At each step, we can choose to include the current number at an even index or an odd index and update these two variables accordingly.

def maxAlternatingSum(nums):
    even_idx_sum, odd_idx_sum = 0, 0
    for num in nums:
        even_idx_sum = max(even_idx_sum, odd_idx_sum + num)
        odd_idx_sum = max(odd_idx_sum, even_idx_sum - num)
    return even_idx_sum

# Example usage:
nums = [4, 2, 5, 3]
print(maxAlternatingSum(nums))
public class Solution {
    public long maxAlternatingSum(int[] nums) {
        long even_idx_sum = 0, odd_idx_sum = 0;
        for (int num : nums) {
            even_idx_sum = Math.max(even_idx_sum, odd_idx_sum + num);
            odd_idx_sum = Math.max(odd_idx_sum, even_idx_sum - num);
        }
        return even_idx_sum;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {4, 2, 5, 3};
        System.out.println(sol.maxAlternatingSum(nums));
    }
}
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

long long maxAlternatingSum(vector<int>& nums) {
    long long even_idx_sum = 0, odd_idx_sum = 0;
    for (int num : nums) {
        even_idx_sum = max(even_idx_sum, odd_idx_sum + num);
        odd_idx_sum = max(odd_idx_sum, even_idx_sum - num);
    }
    return even_idx_sum;
}

int main() {
    vector<int> nums = {4, 2, 5, 3};
    cout << maxAlternatingSum(nums) << endl;
    return 0;
}
function maxAlternatingSum(nums) {
    let even_idx_sum = 0, odd_idx_sum = 0;
    for (let num of nums) {
        const temp_even = even_idx_sum;
        even_idx_sum = Math.max(even_idx_sum, odd_idx_sum + num);
        odd_idx_sum = Math.max(odd_idx_sum, temp_even - num);
    }
    return even_idx_sum;
}

// Example usage:
console.log(maxAlternatingSum([4, 2, 5, 3]));
#include <stdio.h>

long long maxAlternatingSum(int* nums, int numsSize) {
    long long even_idx_sum = 0, odd_idx_sum = 0;
    for (int i = 0; i < numsSize; ++i) {
        even_idx_sum = fmax(even_idx_sum, odd_idx_sum + nums[i]);
        odd_idx_sum = fmax(odd_idx_sum, even_idx_sum - nums[i]);
    }
    return even_idx_sum;
}

int main() {
    int nums[] = {4, 2, 5, 3};
    int size = sizeof(nums)/sizeof(nums[0]);
    printf("%lld\n", maxAlternatingSum(nums, size));
    return 0;
}
using System;

public class Solution {
    public long MaxAlternatingSum(int[] nums) {
        long even_idx_sum = 0, odd_idx_sum = 0;
        foreach (int num in nums) {
            even_idx_sum = Math.Max(even_idx_sum, odd_idx_sum + num);
            odd_idx_sum = Math.Max(odd_idx_sum, even_idx_sum - num);
        }
        return even_idx_sum;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] nums = {4, 2, 5, 3};
        Console.WriteLine(solution.MaxAlternatingSum(nums));
    }
}

In Python, the code uses two variables to maintain the best possible sums for even and odd indices. Each number in the array is evaluated to update these values. The return value is derived from 'even_idx_sum' providing the maximum alternating sum for a subsequence.

Complexity

Time Complexity: O(n) since the function traverses through nums once.
Space Complexity: O(1) due to the use of only two extra variables for computation.

Try this approach in the editor

Approach 2: Greedy Approach with Two Accumulators

This greedy method maintains two accumulators simulating the addition or subtraction at either even or odd positions. The focus is on extracting the optimal number into the alternating sequence while transforming previously computed accumulations successively as per requirement.

def maxAlternatingSum(nums):
    change_to_even, change_to_odd = 0, 0
    for num in nums:
        new_change_to_even = change_to_odd + num
        new_change_to_odd = change_to_even - num
        change_to_even = max(change_to_even, new_change_to_even)
        change_to_odd = max(change_to_odd, new_change_to_odd)
    return change_to_even

# Example usage:
nums = [4, 2, 5, 3]
print(maxAlternatingSum(nums))
public class Solution {
    public long maxAlternatingSum(int[] nums) {
        long change_to_even = 0, change_to_odd = 0;
        for (int num : nums) {
            long new_change_to_even = change_to_odd + num;
            long new_change_to_odd = change_to_even - num;
            change_to_even = Math.max(change_to_even, new_change_to_even);
            change_to_odd = Math.max(change_to_odd, new_change_to_odd);
        }
        return change_to_even;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {4, 2, 5, 3};
        System.out.println(sol.maxAlternatingSum(nums));
    }
}
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

long long maxAlternatingSum(vector<int>& nums) {
    long long change_to_even = 0, change_to_odd = 0;
    for (int num : nums) {
        long long new_change_to_even = change_to_odd + num;
        long long new_change_to_odd = change_to_even - num;
        if (new_change_to_even > change_to_even)
            change_to_even = new_change_to_even;
        if (new_change_to_odd > change_to_odd)
            change_to_odd = new_change_to_odd;
    }
    return change_to_even;
}

int main() {
    vector<int> nums = {4, 2, 5, 3};
    cout << maxAlternatingSum(nums) << endl;
    return 0;
}
function maxAlternatingSum(nums) {
    let change_to_even = 0, change_to_odd = 0;
    for (let num of nums) {
        const new_change_to_even = change_to_odd + num;
        const new_change_to_odd = change_to_even - num;
        change_to_even = Math.max(change_to_even, new_change_to_even);
        change_to_odd = Math.max(change_to_odd, new_change_to_odd);
    }
    return change_to_even;
}

// Example usage:
console.log(maxAlternatingSum([4, 2, 5, 3]));
#include <stdio.h>

long long maxAlternatingSum(int* nums, int numsSize) {
    long long change_to_even = 0, change_to_odd = 0;
    for (int i = 0; i < numsSize; ++i) {
        long long new_change_to_even = change_to_odd + nums[i];
        long long new_change_to_odd = change_to_even - nums[i];
        if (new_change_to_even > change_to_even)
            change_to_even = new_change_to_even;
        if (new_change_to_odd > change_to_odd)
            change_to_odd = new_change_to_odd;
    }
    return change_to_even;
}

int main() {
    int nums[] = {4, 2, 5, 3};
    int size = sizeof(nums)/sizeof(nums[0]);
    printf("%lld\n", maxAlternatingSum(nums, size));
    return 0;
}
using System;

public class Solution {
    public long MaxAlternatingSum(int[] nums) {
        long change_to_even = 0, change_to_odd = 0;
        foreach (int num in nums) {
            long new_change_to_even = change_to_odd + num;
            long new_change_to_odd = change_to_even - num;
            change_to_even = Math.Max(change_to_even, new_change_to_even);
            change_to_odd = Math.Max(change_to_odd, new_change_to_odd);
        }
        return change_to_even;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] nums = {4, 2, 5, 3};
        Console.WriteLine(solution.MaxAlternatingSum(nums));
    }
}

Python's method commences with changing-to accruals altered on iterating each number, configuring to progress adaptation with summed sequences. Capitalizing on max transitions, the whole arrangement surfaces proficiently.

Complexity

Time Complexity: O(n) for inspecting each item in nums.
Space Complexity: O(1) entails minimal auxiliary memory.

Try this approach in the editor

Approach 3: Default Approach

function maxAlternatingSum(nums: number[]): number {
    const n = nums.length;
    const f: number[] = new Array(n + 1).fill(0);
    const g = f.slice();
    for (let i = 1; i <= n; ++i) {
        f[i] = Math.max(g[i - 1] + nums[i - 1], f[i - 1]);
        g[i] = Math.max(f[i - 1] - nums[i - 1], g[i - 1]);
    }
    return Math.max(f[n], g[n]);
}
func maxAlternatingSum(nums []int) int64 {
	n := len(nums)
	f := make([]int, n+1)
	g := make([]int, n+1)
	for i, x := range nums {
		i++
		f[i] = max(g[i-1]-x, f[i-1])
		g[i] = max(f[i-1]+x, g[i-1])
	}
	return int64(max(f[n], g[n]))
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n) since the function traverses through nums once.
Space Complexity: O(1) due to the use of only two extra variables for computation.

Greedy Approach with Two Accumulators

Time Complexity: O(n) for inspecting each item in nums.
Space Complexity: O(1) entails minimal auxiliary memory.

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (State Transition)O(n)O(1)Best for understanding the problem formally using DP states for add and subtract positions
Greedy with Two AccumulatorsO(n)O(1)Preferred interview solution; simple implementation with constant memory

Frequently asked questions

Is Maximum Alternating Subsequence Sum easy or hard?

Maximum Alternating Subsequence Sum is classified as a Medium problem on LeetCode. The challenge lies in recognizing the alternating state pattern and converting the dynamic programming idea into a constant-space implementation.

How to solve Maximum Alternating Subsequence Sum in O(n)?

Maintain two variables: one for the best alternating sum when the next element will be added and another when it will be subtracted. For every number in the array, update these states using the previous values. This single-pass dynamic update yields an O(n) time and O(1) space solution.

Maximum Alternating Subsequence Sum Python or Java solution?

The optimal implementation in Python or Java uses two variables to track add and subtract states while iterating through the array. Each step updates the states using max transitions, producing an O(n) time and O(1) space solution.

What is the best approach for Maximum Alternating Subsequence Sum?

The best approach uses two dynamic states representing the best sum when the next operation is addition or subtraction. This can be implemented either as dynamic programming or a greedy two-accumulator method. Both run in O(n) time and O(1) space while scanning the array once.

What data structure is used in Maximum Alternating Subsequence Sum?

The problem mainly relies on array traversal and dynamic programming states. No complex data structures are required—only two variables that track the best sums for alternating positions.

What is the time complexity of Maximum Alternating Subsequence Sum?

The optimal solution runs in O(n) time because each element in the array is processed exactly once. Only two running states are maintained, so the space complexity is O(1).

Is Maximum Alternating Subsequence Sum asked at Google, Amazon, or Meta?

This problem reflects a common dynamic programming pattern used in interviews at companies like Amazon, Google, and Meta. The alternating state transition is closely related to stock trading DP problems, which frequently appear in technical interviews.

Comments

Next problem · similarMaximum Alternating Subarray SumMedium
Now write it yourselfClose this page and solve Maximum Alternating Subsequence Sum in the editor, without looking.
Practise Maximum Alternating Subsequence Sum