Welcome to Subscribe On Youtube

1911. Maximum Alternating Subsequence Sum

Description

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.

 

Example 1:

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

Example 2:

Input: nums = [5,6,7,8]
Output: 8
Explanation: It is optimal to choose the subsequence [8] with alternating sum 8.

Example 3:

Input: nums = [6,2,1,2,4,5]
Output: 10
Explanation: It is optimal to choose the subsequence [6,1,5] with alternating sum (6 + 5) - 1 = 10.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Solutions

Solution 1: Dynamic Programming

We define $f[i]$ to represent the maximum alternating sum of a subsequence selected from the first $i$ elements, and the last element is an odd subscript, and $g[i]$ to represent the maximum alternating sum of a subsequence selected from the first $i$ elements, and the last element is an even subscript. Initially $f[0] = g[0] = 0$. The answer is $max(f[n], g[n])$.

We consider the $i$ element $nums[i - 1]$:

If the element is selected and it has an odd index, the previous element must be an even index and can only be selected from the first $i-1$ elements, so $f[i] = g[i - 1] - nums[i - 1]$; if the element is not selected, then $f[i] = f[i - 1]$.

Similarly, if the element is selected and the element has an even index, then the previous element must have an odd index and can only be selected from the first $i-1$ elements, so $g[i] = f[i - 1] + nums[i - 1]$; if the element is not selected, then $g[i] = g[i - 1]$.

To sum up, we can get the state transition equation:

\[\begin{aligned} f[i] &= max(g[i - 1] - nums[i - 1], f[i - 1]) \\ g[i] &= max(f[i - 1] + nums[i - 1], g[i - 1]) \end{aligned}\]

The final answer is $max(f[n], g[n])$.

We note that $f[i]$ and $g[i]$ are only related to $f[i - 1]$ and $g[i - 1]$, so we can use two variables instead of arrays, reducing the space complexity to $O(1)$.

Time complexity $O(n)$, where $n$ is the array length.

Solution 2

This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

  • class Solution {
    public long maxAlternatingSum(int[] nums) {
        int n = nums.length;
        long[] f = new long[n + 1];
        long[] g = new long[n + 1];
        for (int i = 1; i <= n; ++i) {
            f[i] = Math.max(g[i - 1] - nums[i - 1], f[i - 1]);
            g[i] = Math.max(f[i - 1] + nums[i - 1], g[i - 1]);
        }
        return Math.max(f[n], g[n]);
    }
}


// Solution 2
class Solution {
    public long maxAlternatingSum(int[] nums) {
        long f = 0, g = 0;
        for (int x : nums) {
            long ff = Math.max(g - x, f);
            long gg = Math.max(f + x, g);
            f = ff;
            g = gg;
        }
        return Math.max(f, g);
    }
}


  • class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        int n = nums.size();
        vector<long long> f(n + 1), g(n + 1);
        for (int i = 1; i <= n; ++i) {
            f[i] = max(g[i - 1] - nums[i - 1], f[i - 1]);
            g[i] = max(f[i - 1] + nums[i - 1], g[i - 1]);
        }
        return max(f[n], g[n]);
    }
};


// Solution 2
class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        long long f = 0, g = 0;
        for (int& x : nums) {
            long ff = max(g - x, f), gg = max(f + x, g);
            f = ff, g = gg;
        }
        return max(f, g);
    }
};


  • class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        n = len(nums)
        f = [0] * (n + 1)
        g = [0] * (n + 1)
        for i, x in enumerate(nums, 1):
            f[i] = max(g[i - 1] - x, f[i - 1])
            g[i] = max(f[i - 1] + x, g[i - 1])
        return max(f[n], g[n])


# Solution 2
class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        f = g = 0
        for x in nums:
            f, g = max(g - x, f), max(f + x, g)
        return max(f, g)


  • func maxAlternatingSum(nums []int) int64 {
	n := len(nums)
	f := make([]int, n+1)
	g := make([]int, n+1)
	for i, x := range nums {
		i++
		f[i] = max(g[i-1]-x, f[i-1])
		g[i] = max(f[i-1]+x, g[i-1])
	}
	return int64(max(f[n], g[n]))
}


// Solution 2
func maxAlternatingSum(nums []int) int64 {
	var f, g int
	for _, x := range nums {
		f, g = max(g-x, f), max(f+x, g)
	}
	return int64(max(f, g))
}


  • function maxAlternatingSum(nums: number[]): number {
    const n = nums.length;
    const f: number[] = new Array(n + 1).fill(0);
    const g = f.slice();
    for (let i = 1; i <= n; ++i) {
        f[i] = Math.max(g[i - 1] + nums[i - 1], f[i - 1]);
        g[i] = Math.max(f[i - 1] - nums[i - 1], g[i - 1]);
    }
    return Math.max(f[n], g[n]);
}


// Solution 2
function maxAlternatingSum(nums: number[]): number {
    let [f, g] = [0, 0];
    for (const x of nums) {
        [f, g] = [Math.max(g - x, f), Math.max(f + x, g)];
    }
    return g;
}

All Problems

All Solutions