Maximum Alternating Subsequence Sum

Medium
1146.

Maximum Alternating Subsequence Sum

Maximum Alternating Subsequence Sum is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

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^4
  • 1 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAlternatingSum = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 1 <= nums[i] <= 10^5

Hints for Maximum Alternating Subsequence Sum

  1. Hint 1

    Process elements left to right. At each point, a partial subsequence has either just added an element or just subtracted one.

  2. 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).

  3. Hint 3

    For each x: added = max(added, subtracted + x) and subtracted = max(subtracted, added - x); the answer is the final added.

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

  1. Let added = 0 and subtracted = 0 (the empty subsequence).
  2. For each element x, compute newAdded = max(added, subtracted + x) and newSubtracted = max(subtracted, added - x) from the old values.
  3. Assign both and continue.
  4. 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 added first and then using it for subtracted lets an element be taken twice.
  • Equivalently, the answer is nums[0] plus every positive rise nums[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 added

Java

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