Maximum Alternating Subsequence Sum — Problem & Solution
Maximum Alternating Subsequence Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Alternating Subsequence Sum is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The alternating sum of a sequence is the sum of the elements at even positions minus the sum of the elements at odd positions (0-indexed). For example, the alternating sum of [4,2,5,3] is (4 + 5) - (2 + 3) = 4.
Pick a subsequence of nums (delete any elements, keep the order; positions are re-indexed from 0) and return the maximum alternating sum it can have.
CodeKairo bounds: the array is shorter than in the original problem so that the answer fits in a 32-bit integer.
Example 1
Input: nums = [3,1,4]
Output: 6
Explanation: Take all three: `3 - 1 + 4`.
Example 2
Input: nums = [5,4,3]
Output: 5
Explanation: Take just `[5]`.
Example 3
Input: nums = [1,6,2,7]
Output: 11
Explanation: `[6,2,7]` gives `6 - 2 + 7`.
Constraints
1 <= nums.length <= 10^41 <= nums[i] <= 10^5
Hints for Maximum Alternating Subsequence Sum
Hint 1
Process elements left to right. At each point, a partial subsequence has either just added an element or just subtracted one.
Hint 2
Track two values: the best alternating sum whose last element was added, and the best whose last element was subtracted (the empty subsequence counts here with 0).
Hint 3
For each
x:added = max(added, subtracted + x)andsubtracted = max(subtracted, added - x); the answer is the finaladded.
How to solve Maximum Alternating Subsequence Sum
A two-state DP: the best alternating sum so far whose next element would be subtracted, and the one whose next element would be added.
Approach
- Let
added = 0andsubtracted = 0(the empty subsequence). - For each element
x, computenewAdded = max(added, subtracted + x)andnewSubtracted = max(subtracted, added - x)from the old values. - Assign both and continue.
- Return
added.
Why it works
Any subsequence is built by deciding, element by element, to skip or to take; taking flips which sign comes next. added and subtracted hold the best value reachable in each sign state over all choices for the prefix, and the recurrence considers both skipping and taking x. An optimal subsequence never ends on a subtracted element (dropping it increases the sum), so the answer is added.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Update both states from the old values — overwriting
addedfirst and then using it forsubtractedlets an element be taken twice. - Equivalently, the answer is
nums[0]plus every positive risenums[i] - nums[i-1]. - With the original bounds (10^5 elements up to 10^5) the answer needs 64 bits.
Reference solution
Python
from typing import List
def maxAlternatingSum(nums: List[int]) -> int:
added = subtracted = 0
for x in nums:
added, subtracted = max(added, subtracted + x), max(subtracted, added - x)
return addedJava
public static int maxAlternatingSum(int[] nums) {
long added = 0, subtracted = 0;
for (int x : nums) {
long newAdded = Math.max(added, subtracted + x);
long newSubtracted = Math.max(subtracted, added - x);
added = newAdded;
subtracted = newSubtracted;
}
return (int) added;
}C++
int maxAlternatingSum(vector<int>& nums) {
long long added = 0, subtracted = 0;
for (int x : nums) {
long long newAdded = max(added, subtracted + x);
long long newSubtracted = max(subtracted, added - x);
added = newAdded;
subtracted = newSubtracted;
}
return (int)added;
}JavaScript
var maxAlternatingSum = function(nums) {
var added = 0, subtracted = 0;
for (var i = 0; i < nums.length; i++) {
var x = nums[i];
var newAdded = Math.max(added, subtracted + x);
var newSubtracted = Math.max(subtracted, added - x);
added = newAdded;
subtracted = newSubtracted;
}
return added;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming