Maximum Alternating Subsequence Sum
MedPrompt
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 <= 1051 <= nums[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming with a straightforward state definition. We build two arrays, dp_even and dp_odd, to keep track of the maximum alternating sum for subsequences ending at each index i. dp_even[i] stores the maximum sum where nums[i] is at an even position (added), and dp_odd[i] is for when nums[i] is at an odd position (subtracted). To compute the value for index i, we must iterate through all previous indices j < i to find the optimal subsequence to extend. This leads to a nested loop structure and a quadratic time complexity.
Algorithm
- Initialize two DP arrays,
dp_evenanddp_odd, of sizen. dp_even[i]will store the maximum alternating sum of a subsequence fromnums[0...i]that ends withnums[i]at an even-indexed position.dp_odd[i]will store the maximum alternating sum of a subsequence fromnums[0...i]that ends withnums[i]at an odd-indexed position.- Iterate through the
numsarray fromi = 0ton-1:- To calculate
dp_even[i],nums[i]can either start a new subsequence (sumnums[i]) or be appended to a subsequence that ended atj < iat an odd position. We take the maximum over all possiblej. The recurrence is:dp_even[i] = nums[i] + max(0, max_{j<i} dp_odd[j]). - To calculate
dp_odd[i],nums[i]must be appended to a subsequence that ended atj < iat an even position. The recurrence is:dp_odd[i] = -nums[i] + max_{j<i} dp_even[j].
- To calculate
- The final answer is the maximum value in the
dp_evenarray, as any optimal subsequence must have an odd length (since all numbers are positive).
Walkthrough
In this method, we define our DP states based on the last element of the subsequence.
Let dp_even[i] be the maximum alternating sum of a subsequence ending with nums[i], where nums[i] is at an even position (0-indexed) in the subsequence.
Let dp_odd[i] be the maximum alternating sum of a subsequence ending with nums[i], where nums[i] is at an odd position in the subsequence.
For each element nums[i], we calculate dp_even[i] and dp_odd[i]:
- To get
dp_even[i],nums[i]is added. It can either be the first element of a new subsequence (sumnums[i]) or be appended to an existing subsequence that had an even number of elements. To maximize the sum, we find the maximumdp_odd[j]for allj < iand addnums[i]to it. So,dp_even[i] = nums[i] + max(0, max_{j<i} dp_odd[j]). - To get
dp_odd[i],nums[i]is subtracted. It must be appended to an existing subsequence that had an odd number of elements. We find the maximumdp_even[j]for allj < iand subtractnums[i]from it. So,dp_odd[i] = -nums[i] + max_{j<i} dp_even[j].
After filling the DP arrays, the answer is the maximum value across the entire dp_even array. The nested loops required to find the maximum of previous states make this an O(N^2) solution.
public long maxAlternatingSum(int[] nums) { int n = nums.length; if (n == 0) { return 0; } long[] dp_even = new long[n]; long[] dp_odd = new long[n]; long max_sum = 0; for (int i = 0; i < n; i++) { long max_prev_odd = 0; for (int j = 0; j < i; j++) { max_prev_odd = Math.max(max_prev_odd, dp_odd[j]); } dp_even[i] = (long)nums[i] + max_prev_odd; long max_prev_even = 0; for (int j = 0; j < i; j++) { max_prev_even = Math.max(max_prev_even, dp_even[j]); } // An odd-positioned element must follow an even-positioned one. if (max_prev_even > 0) { dp_odd[i] = max_prev_even - nums[i]; } else { // Cannot form a valid subsequence of length > 1 ending at i in an odd position dp_odd[i] = Long.MIN_VALUE; } max_sum = Math.max(max_sum, dp_even[i]); } return max_sum;}Complexity
Time
O(N^2), where N is the number of elements in `nums`. For each element, we iterate through all previous elements to find the maximums, leading to a nested loop.
Space
O(N), where N is the number of elements in `nums`. We use two arrays of size N to store the DP states.
Trade-offs
Pros
It's a valid DP approach that correctly solves the problem.
It's more efficient than a brute-force exponential solution.
Cons
The O(N^2) time complexity is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
This approach improves upon the O(N^2) DP solution by refining the state definition. Instead of tracking subsequences that end at index i, we track the best possible subsequence sum using elements up to index i. This change allows us to formulate a recurrence relation that only depends on the results from the immediately preceding index, i-1. This eliminates the need for the inner loop and reduces the time complexity to linear, O(N).
Algorithm
- Define two DP arrays,
evenandodd, of sizen. even[i]will store the maximum alternating sum of any subsequence fromnums[0...i]that has an odd number of elements.odd[i]will store the maximum alternating sum of any subsequence fromnums[0...i]that has an even number of elements.- Initialize base cases:
even[0] = nums[0]andodd[0] = 0. - Iterate from
i = 1ton-1:even[i] = max(even[i-1], odd[i-1] + nums[i]). This considers either not takingnums[i]or taking it at an even position.odd[i] = max(odd[i-1], even[i-1] - nums[i]). This considers either not takingnums[i]or taking it at an odd position.
- The final answer is
even[n-1].
Walkthrough
We can optimize the DP by changing the state definition. Let even[i] be the maximum alternating sum of a subsequence from nums[0...i] having an odd length, and odd[i] be the maximum for a subsequence with an even length.
When considering nums[i], we have two choices:
- Don't include
nums[i]: The maximum sums remain the same as ati-1. So,even[i-1]andodd[i-1]are candidates. - Include
nums[i]:- To form a new odd-length subsequence, we must add
nums[i]. This means it's appended to a previous even-length subsequence. The best we can do isodd[i-1] + nums[i]. - To form a new even-length subsequence, we must subtract
nums[i]. This means it's appended to a previous odd-length subsequence. The best we can do iseven[i-1] - nums[i].
- To form a new odd-length subsequence, we must add
Combining these choices gives the recurrence relations:
even[i] = max(even[i-1], odd[i-1] + nums[i])odd[i] = max(odd[i-1], even[i-1] - nums[i])
The base case is even[0] = nums[0] (subsequence [nums[0]]) and odd[0] = 0 (empty subsequence). The final answer is even[n-1], as the maximum sum will always come from an odd-length subsequence.
public long maxAlternatingSum(int[] nums) { int n = nums.length; if (n == 0) { return 0; } long[] even = new long[n]; long[] odd = new long[n]; even[0] = nums[0]; // odd[0] is implicitly 0, representing an empty subsequence for (int i = 1; i < n; i++) { even[i] = Math.max(even[i - 1], odd[i - 1] + nums[i]); odd[i] = Math.max(odd[i - 1], even[i - 1] - nums[i]); } return even[n - 1];}Complexity
Time
O(N), as we perform a single pass through the input array.
Space
O(N), for the two DP arrays `even` and `odd`.
Trade-offs
Pros
Achieves a linear time complexity, which is very efficient.
The logic is a direct and clear representation of the choices at each step.
Cons
While efficient in time, it uses O(N) extra space, which is not optimal for this problem.
This is the most efficient solution. It refines the linear DP approach by observing that the calculations for the current state i only depend on the state at i-1. This means we don't need to store the entire history in DP arrays. We can use just two variables to keep track of the latest maximum alternating sums for odd-length and even-length subsequences. This reduces the space complexity to a constant O(1) while maintaining the linear time complexity.
Algorithm
- Initialize two variables:
even = 0(for max sum of odd-length subsequences) andodd = 0(for max sum of even-length subsequences). - Iterate through each number
numin thenumsarray:- Store the current
evenvalue in a temporary variable, e.g.,prev_even. - Update
even:even = max(even, odd + num). This decides whether to extend an even-length subsequence withnumor stick with the best odd-length subsequence found so far. - Update
odd:odd = max(odd, prev_even - num). This decides whether to extend an odd-length subsequence (using its old valueprev_even) or stick with the best even-length subsequence.
- Store the current
- After iterating through all numbers, return
even.
Walkthrough
This approach is a space optimization of the linear time DP. Since even[i] and odd[i] only depend on even[i-1] and odd[i-1], we can get rid of the arrays and use only two variables.
Let even be the maximum alternating sum for an odd-length subsequence found so far.
Let odd be the maximum alternating sum for an even-length subsequence found so far.
We initialize both even and odd to 0, representing the sum of an empty subsequence. Then, we iterate through each number num in nums and update our variables:
- The new maximum
evensum is either the existingevensum (if we don't includenum) orodd + num(if we includenumat an even position). - The new maximum
oddsum is either the existingoddsum oreven - num. Crucially, when calculating the newodd, we must use theevenvalue from before it was updated in the current step.
This logic can be seen as finding peaks and valleys. even tracks the maximum profit ending with a sale (a peak), and odd tracks the state after a purchase (a valley). The final answer is the maximum even sum after processing all numbers.
public long maxAlternatingSum(int[] nums) { long even = 0; // Represents the max sum for a subsequence of odd length long odd = 0; // Represents the max sum for a subsequence of even length for (int num : nums) { // Store the previous 'even' state before it's updated long prev_even = even; // The new max 'even' sum is either the old 'even' sum (don't pick num), // or the old 'odd' sum + num (pick num at an even position). even = Math.max(even, odd + num); // The new max 'odd' sum is either the old 'odd' sum (don't pick num), // or the 'even' sum from the previous state - num (pick num at an odd position). odd = Math.max(odd, prev_even - num); } return even;}Complexity
Time
O(N), for a single pass over the input array.
Space
O(1), as we only use a constant number of variables regardless of the input size.
Trade-offs
Pros
Optimal O(N) time complexity.
Optimal O(1) space complexity.
The implementation is simple and concise.
Cons
There are no significant cons to this approach as it is optimal in both time and space.
Solutions
Solution
class Solution {public long maxAlternatingSum(int[] nums) { int n = nums.length; long[] f = new long[n + 1]; long[] g = new long[n + 1]; for (int 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]); }}class Solution {public: long long maxAlternatingSum(vector<int> &nums) { int n = nums.size(); vector<long long> f(n + 1), g(n + 1); for (int i = 1; i <= n; ++i) { f[i] = max(g[i - 1] - nums[i - 1], f[i - 1]); g[i] = max(f[i - 1] + nums[i - 1], g[i - 1]); } return max(f[n], g[n]); }};class Solution: def maxAlternatingSum(self, nums: List[int]) -> int: n = len(nums) f = [0] * (n + 1) g = [0] * (n + 1) for i, x in enumerate(nums, 1): f[i] = max(g[i - 1] - x, f[i - 1]) g[i] = max(f[i - 1] + x, g[i - 1]) return max(f[n], g[n])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.