Maximum Alternating Subarray Sum solution and explanation
The problem
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).
class Solution:
def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:
ans = f = g = -inf
for x in nums:
f, g = max(g, 0) + x, f - x
ans = max(ans, f, g)
return ansclass Solution {
public long maximumAlternatingSubarraySum(int[] nums) {
final long inf = 1L << 60;
long ans = -inf, f = -inf, g = -inf;
for (int x : nums) {
long ff = Math.max(g, 0) + x;
g = f - x;
f = ff;
ans = Math.max(ans, Math.max(f, g));
}
return ans;
}
}class Solution {
public:
long long maximumAlternatingSubarraySum(vector<int>& nums) {
using ll = long long;
const ll inf = 1LL << 60;
ll ans = -inf, f = -inf, g = -inf;
for (int x : nums) {
ll ff = max(g, 0LL) + x;
g = f - x;
f = ff;
ans = max({ans, f, g});
}
return ans;
}
};function maximumAlternatingSubarraySum(nums: number[]): number {
let [ans, f, g] = [-Infinity, -Infinity, -Infinity];
for (const x of nums) {
[f, g] = [Math.max(g, 0) + x, f - x];
ans = Math.max(ans, f, g);
}
return ans;
}func maximumAlternatingSubarraySum(nums []int) int64 {
const inf = 1 << 60
ans, f, g := -inf, -inf, -inf
for _, x := range nums {
f, g = max(g, 0)+x, f-x
ans = max(ans, max(f, g))
}
return int64(ans)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Simulation | O(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 |
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.