Skip to main content
Talentd

Maximum Alternating Subarray Sum - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic Programming7 min readAsked at: Amazon
Practice this problem

Problem Statement

A subarray of a 0-indexed integer array is a contiguous non-empty sequence of elements within an array.

The alternating subarray sum of a subarray that ranges from index i to j (inclusive, 0 <= i <= j < nums.length) is nums[i] - nums[i+1] + nums[i+2] - ... +/- nums[j].

Given a 0-indexed integer array nums, return the maximum alternating subarray sum of any subarray of nums.

 

Example 1:

Input: nums = [3,-1,1,2]
Output: 5
Explanation:
The subarray [3,-1,1] has the largest alternating subarray sum.
The alternating subarray sum is 3 - (-1) + 1 = 5.

Example 2:

Input: nums = [2,2,2,2,2]
Output: 2
Explanation:
The subarrays [2], [2,2,2], and [2,2,2,2,2] have the largest alternating subarray sum.
The alternating subarray sum of [2] is 2.
The alternating subarray sum of [2,2,2] is 2 - 2 + 2 = 2.
The alternating subarray sum of [2,2,2,2,2] is 2 - 2 + 2 - 2 + 2 = 2.

Example 3:

Input: nums = [1]
Output: 1
Explanation:
There is only one non-empty subarray, which is [1].
The alternating subarray sum is 1.

 

Constraints:

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

Approach Overview

Problem Overview: You are given an integer array and must find a subarray where the sum alternates between addition and subtraction: a[l] - a[l+1] + a[l+2] - a[l+3] .... The goal is to return the maximum possible alternating sum among all subarrays.

Approach 1: Brute Force Subarray Simulation (O(n²) time, O(1) space)

Enumerate every possible subarray starting index i. For each start, extend the subarray one element at a time and maintain a running alternating sum. Use a boolean or parity flag to switch between addition and subtraction at every step. Track the maximum value encountered across all subarrays. This approach works because it explicitly checks every valid candidate, but it performs roughly n(n+1)/2 subarray evaluations, making it too slow for large inputs.

Approach 2: Dynamic Programming (Kadane-style Alternating States) (O(n) time, O(1) space)

The optimal solution treats this as a variation of the classic maximum subarray problem from dynamic programming. Instead of tracking one running sum, maintain two states while iterating through the array:

even represents the best alternating sum of a subarray ending at the current index where the element is added (positive sign). odd represents the best sum where the element is subtracted (negative sign). When processing nums[i], either start a new subarray with nums[i] as the first positive term, or extend a previous alternating pattern.

The transitions are straightforward. A positive position can either start fresh (nums[i]) or extend a previous negative state (odd + nums[i]). A negative position must follow a positive state (even_prev - nums[i]). While iterating once through the array, update both states and track the global maximum. This works because every valid alternating subarray must alternate between these two states.

This DP compresses all possible subarrays into constant state variables and avoids recomputation. The result is a linear scan with constant extra memory, which is optimal for this problem.

Recommended for interviews: Start by describing the brute force enumeration to demonstrate understanding of the alternating pattern constraint. Then move to the Kadane-style dynamic programming optimization. Interviewers typically expect the O(n) DP solution because it shows you can model state transitions and optimize subarray problems efficiently.

Solution

We define f as the maximum sum of the alternating subarray ending with nums[i], and define g as the maximum sum of the alternating subarray ending with -nums[i]. Initially, both f and g are -infty.

Next, we traverse the array nums. For position i, we need to maintain the values of f and g, i.e., f = max(g, 0) + nums[i], and g = f - nums[i]. The answer is the maximum value among all f and g.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray SimulationO(n²)O(1)Useful for understanding the alternating pattern and validating logic on small inputs
Dynamic Programming (Kadane-style Alternating States)O(n)O(1)Best choice for interviews and production solutions where linear performance is required

Video Solution

2036. Maximum Alternating Subarray Sum (Leetcode Medium) • Programming Live with Larry • 846 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Maximum Alternating Subarray Sum easy or hard?
Maximum Alternating Subarray Sum is generally classified as a Medium problem. The difficulty comes from recognizing the alternating sign constraint and converting the problem into a Kadane-style dynamic programming state transition.
Maximum Alternating Subarray Sum Python/Java solution
The typical Python or Java solution uses two variables to store the current positive and negative alternating sums. Iterate through the array, update the two states using DP transitions, and track the maximum value seen. This implementation runs in O(n) time and O(1) extra space.
How to solve Maximum Alternating Subarray Sum in O(n)?
Maintain two DP states while iterating through the array: one for subarrays ending with a positive contribution and one for those ending with a negative contribution. Update the positive state using max(nums[i], odd + nums[i]) and update the negative state using even_prev - nums[i]. Track the maximum positive state across the traversal to obtain the answer in linear time.
What is the best approach for Maximum Alternating Subarray Sum?
The optimal approach uses dynamic programming with two running states representing alternating signs. Track the best sum where the current element is added (even position) and where it is subtracted (odd position). Updating these states while scanning the array once yields an O(n) time and O(1) space solution.
Is Maximum Alternating Subarray Sum asked at Google/Amazon/Meta?
Alternating sum and Kadane-style dynamic programming problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this question test your ability to model state transitions and optimize subarray computations.
What data structure is used in Maximum Alternating Subarray Sum?
The problem primarily relies on dynamic programming with constant variables rather than complex data structures. The input is processed as a simple array while maintaining two DP states representing alternating sign positions.
What is the time complexity of Maximum Alternating Subarray Sum?
The optimal dynamic programming solution runs in O(n) time because the array is processed exactly once. Only two variables are maintained for the alternating states, so the space complexity remains O(1). A naive brute force approach that evaluates every subarray takes O(n^2) time.

Ready to solve this problem?

Practice Maximum Alternating Subarray Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Alternating Subsequence Sum