Watch 3 video solutions for Maximum Alternating Subarray Sum, a medium level problem involving Array, Dynamic Programming. This walkthrough by Programming Live with Larry has 826 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 105Problem 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.
| 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 |