Maximum Alternating Subsequence Sum

medium dp greedy

Problem

Pick a subsequence to maximize (sub[0] − sub[1] + sub[2] − …).

Inputnums = [4,2,5,3]

Output7

Pick 4,2,5,3 → 4−2+5−3 = 4? Actually pick 4 and 3 → 4+3−... ; best is 5: optimal subsequence [5,3] gives 5; or [4,2,5,3] gives 4−2+5−3=4. Best is 7 by picking [4,2,5] → 4−2+5=7.

nums

def max_alternating_sum(nums):
    even = 0  # last picked at even index
    odd = 0   # last picked at odd index
    for x in nums:
        even, odd = max(even, odd + x), max(odd, even - x)
    return even

function maxAlternatingSum(nums) {
  let even = 0, odd = 0;
  for (const x of nums) {
    const ne = Math.max(even, odd + x), no = Math.max(odd, even - x);
    even = ne; odd = no;
  }
  return even;
}

class Solution {
    public long maxAlternatingSum(int[] nums) {
        long even = 0, odd = 0;
        for (int x : nums) {
            long ne = Math.max(even, odd + x), no = Math.max(odd, even - x);
            even = ne; odd = no;
        }
        return even;
    }
}

long long maxAlternatingSum(vector<int>& nums) {
    long long even = 0, odd = 0;
    for (int x : nums) {
        long long ne = max(even, odd + (long long) x), no = max(odd, even - (long long) x);
        even = ne; odd = no;
    }
    return even;
}

Explanation

We are building a subsequence whose value alternates plus, minus, plus, minus. The neat trick is to realize that at any moment we only care about two running totals: the best alternating sum where the next pick would be added, and the best where it would be subtracted.

Call them even (we have picked an even count so far, so the next element is added) and odd (odd count picked, next would be subtracted). Both start at 0, meaning we have taken nothing.

For each value x we update both. The new even is the better of skipping x or taking it as an added element on top of an odd state: max(even, odd + x). The new odd is the better of skipping or taking x as a subtracted element on top of an even state: max(odd, even - x).

This works because every element either joins the subsequence in the correct alternating slot or is skipped, and the two states always hold the best achievable so far for each parity. The final answer is even, since a best subsequence ends ready for the next add.

Example: for [4,2,5,3], picking 4, 2, 5 gives 4 - 2 + 5 = 7, which the even total reaches as the answer.

Time: O(n) Space: O(1)