1911. Maximum Alternating Subsequence Sum

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.

class Solution {
public:
    long long maxAlternatingSum(vector<int>& A) {
        long long res = 0, n = A.size(), inc = 0, dec = 0;
        for(int i = n - 1; i >= 0; i--) {
            res = max(res, A[i] + dec);
            long long dtemp = dec;
            dec = max(dec, -A[i] + inc);
            inc = max(inc, A[i] + dtemp);
        }
        return res;
    }
};