Maximum Alternating Subsequence Sum - Leetcode Solution

Problem Statement:

Given an array nums of integers, find the maximum alternating subsequence sum of any subsequence of nums.

A subsequence of an array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4].

The alternating sum of a subsequence [nums[i1], nums[i2], ..., nums[ik]] of nums is the sum of (-1)^0 * nums[i1] + (-1)^1 * nums[i2] + (-1)^2 * nums[i3] + ... + (-1)^(k-1) * nums[ik].

For example, the alternating sum of [1,4,2,5] is 1 - 4 + 2 - 5 = -6, and the alternating sum of [5,3,9] is 5 - 3 + 9 = 11.

Return the maximum alternating sum of any subsequence of nums.

Input: nums = [4,2,5,3] Output: 7 Explanation: It is optimal to choose the subsequence [4,2,5] with alternating sum 4 - 2 + 5 = 7.

Solution Approach:

To solve this problem, we will use dynamic programming. We will create two arrays dp1 and dp2, where dp1[i] represents the maximum alternating sum of any subsequence that ends with the element nums[i], and dp2[i] represents the maximum alternating sum of any subsequence that starts with the element nums[i].

For the first array, we initially set dp1[0] = nums[0] and for remaining elements, we use the recurrence relation dp1[i] = max(dp2[i-1] + nums[i], dp1[i-1]).

Similarly, for the second array, we initially set dp2[n-1] = nums[n-1] and for remaining elements, we use the recurrence relation dp2[i] = max(dp1[i+1] - nums[i], dp2[i+1]).

Finally, we return the maximum value in the dp1 array.

Code Implementation:

class Solution { public: int maxAlternatingSum(vector<int>& nums) { int n = nums.size(); vector<int> dp1(n), dp2(n); dp1[0] = nums[0]; dp2[n-1] = nums[n-1];

    for(int i=1; i<n; i++) {
        dp1[i] = max(dp2[i-1] + nums[i], dp1[i-1]);
    }
    
    for(int i=n-2; i>=0; i--) {
        dp2[i] = max(dp1[i+1] - nums[i], dp2[i+1]);
    }
    
    return dp1[n-1];
}

};

The time complexity of this solution is O(n) and the space complexity is O(n) as well, where n is the size of the input array.

1