Problem

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:

1
2
3

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:

1
2
3

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

Example 3:

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

Solution

Method 1 - Recursive

Intuition

At each index, we can either choose the current element (and alternate the sign for the next index), or skip it (and keep the sign the same). The goal is to maximize the alternating sum by exploring all possible subsequences recursively.

Approach

Define a recursive function that takes the current index and a boolean indicating whether the next element should be added or subtracted. For each call, return the maximum of choosing or skipping the current element. The base case is when the index reaches the end of the array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
	long long dfs(const vector<int>& nums, int idx, bool isPos) {
		if (idx == nums.size()) return 0;
		long long choose = (isPos ? nums[idx] : -nums[idx]) + dfs(nums, idx + 1, !isPos);
		long long skip = dfs(nums, idx + 1, isPos);
		return max(choose, skip);
	}
	long long maxAlternatingSum(vector<int>& nums) {
		return dfs(nums, 0, true);
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func maxAlternatingSum(nums []int) int64 {
	var dfs func(idx int, isPos bool) int64
	dfs = func(idx int, isPos bool) int64 {
		if idx == len(nums) {
			return 0
		}
		choose := int64(nums[idx])
		if !isPos {
			choose = -choose
		}
		choose += dfs(idx+1, !isPos)
		skip := dfs(idx+1, isPos)
		if choose > skip {
			return choose
		}
		return skip
	}
	return dfs(0, true)
}
1
2
3
4
5
6
7
8
9

public long maxAlternatingSum(int[] nums) {
	return dfs(nums, 0, true);
}
private long dfs(int[] nums, int idx, boolean isPos) {
	if (idx == nums.length) return 0;
	long choose = (isPos ? nums[idx] : -nums[idx]) + dfs(nums, idx + 1, !isPos);
	long skip = dfs(nums, idx + 1, isPos);
	return Math.max(choose, skip);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
	fun maxAlternatingSum(nums: IntArray): Long {
		fun dfs(idx: Int, isPos: Boolean): Long {
			if (idx == nums.size) return 0L
			val choose = (if (isPos) nums[idx] else -nums[idx]) + dfs(idx + 1, !isPos)
			val skip = dfs(idx + 1, isPos)
			return maxOf(choose, skip)
		}
		return dfs(0, true)
	}
}
1
2
3
4
5
6
7
8
9

class Solution:
	def maxAlternatingSum(self, nums: list[int]) -> int:
		def dfs(idx: int, is_pos: bool) -> int:
			if idx == len(nums):
				return 0
			choose = (nums[idx] if is_pos else -nums[idx]) + dfs(idx + 1, not is_pos)
			skip = dfs(idx + 1, is_pos)
			return max(choose, skip)
		return dfs(0, True)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
	pub fn max_alternating_sum(nums: Vec<i32>) -> i64 {
		fn dfs(nums: &Vec<i32>, idx: usize, is_pos: bool) -> i64 {
			if idx == nums.len() { return 0; }
			let choose = (if is_pos { nums[idx] } else { -nums[idx] }) as i64 + dfs(nums, idx + 1, !is_pos);
			let skip = dfs(nums, idx + 1, is_pos);
			choose.max(skip)
		}
		dfs(&nums, 0, true)
	}
}
1
2
3
4
5
6
7
8
9

function maxAlternatingSum(nums: number[]): number {
	function dfs(idx: number, isPos: boolean): number {
		if (idx === nums.length) return 0;
		const choose = (isPos ? nums[idx] : -nums[idx]) + dfs(idx + 1, !isPos);
		const skip = dfs(idx + 1, isPos);
		return Math.max(choose, skip);
	}
	return dfs(0, true);
}

Complexity

  • ⏰ Time complexity: O(2^n), where n is the length of nums. Each element can be chosen or skipped, leading to exponential growth.
  • 🧺 Space complexity: O(n), for the recursion stack.

Method 2 - Using Topdown DP Memoization

Intuition

Use memoization to avoid redundant calculations in the recursive approach. Store the maximum alternating sum for each subproblem defined by index and sign in a DP table.

Approach

Define a recursive function with a DP table indexed by position and sign. For each call, check if the result is already computed. If not, compute the maximum alternating sum by considering both choosing and skipping the current element, and store the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
	long long dfs(const vector<int>& nums, int idx, bool isPos, vector<vector<long long>>& dp) {
		if (idx == nums.size()) return 0;
		int posIdx = isPos ? 1 : 0;
		if (dp[posIdx][idx] != -1) return dp[posIdx][idx];
		long long curr = isPos ? nums[idx] : -nums[idx];
		long long choose = curr + dfs(nums, idx + 1, !isPos, dp);
		long long skip = dfs(nums, idx + 1, isPos, dp);
		dp[posIdx][idx] = max(choose, skip);
		return dp[posIdx][idx];
	}
	long long maxAlternatingSum(vector<int>& nums) {
		vector<vector<long long>> dp(2, vector<long long>(nums.size(), -1));
		return dfs(nums, 0, true, dp);
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func maxAlternatingSum(nums []int) int64 {
	dp := make([][]int64, 2)
	for i := range dp {
		dp[i] = make([]int64, len(nums))
		for j := range dp[i] {
			dp[i][j] = -1
		}
	}
	var dfs func(idx int, isPos bool) int64
	dfs = func(idx int, isPos bool) int64 {
		if idx == len(nums) {
			return 0
		}
		posIdx := 0
		if isPos {
			posIdx = 1
		}
		if dp[posIdx][idx] != -1 {
			return dp[posIdx][idx]
		}
		curr := int64(nums[idx])
		if !isPos {
			curr = -curr
		}
		choose := curr + dfs(idx+1, !isPos)
		skip := dfs(idx+1, isPos)
		if choose > skip {
			dp[posIdx][idx] = choose
		} else {
			dp[posIdx][idx] = skip
		}
		return dp[posIdx][idx]
	}
	return dfs(0, true)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public long maxAlternatingSum(int[] nums) {
	long[][] dp = new long[2][nums.length];
	for (int i = 0; i < 2; i++) Arrays.fill(dp[i], -1);
	return dfs(nums, 0, true, dp);
}
private long dfs(int[] nums, int idx, boolean isPos, long[][] dp) {
	if (idx == nums.length) return 0;
	int posIdx = isPos ? 1 : 0;
	if (dp[posIdx][idx] != -1) return dp[posIdx][idx];
	long curr = isPos ? nums[idx] : -nums[idx];
	long choose = curr + dfs(nums, idx + 1, !isPos, dp);
	long skip = dfs(nums, idx + 1, isPos, dp);
	dp[posIdx][idx] = Math.max(choose, skip);
	return dp[posIdx][idx];
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
	fun maxAlternatingSum(nums: IntArray): Long {
		val dp = Array(2) { LongArray(nums.size) { -1L } }
		fun dfs(idx: Int, isPos: Boolean): Long {
			if (idx == nums.size) return 0L
			val posIdx = if (isPos) 1 else 0
			if (dp[posIdx][idx] != -1L) return dp[posIdx][idx]
			val curr = if (isPos) nums[idx].toLong() else -nums[idx].toLong()
			val choose = curr + dfs(idx + 1, !isPos)
			val skip = dfs(idx + 1, isPos)
			dp[posIdx][idx] = maxOf(choose, skip)
			return dp[posIdx][idx]
		}
		return dfs(0, true)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
	def maxAlternatingSum(self, nums: list[int]) -> int:
		dp = [[-1] * len(nums) for _ in range(2)]
		def dfs(idx: int, is_pos: bool) -> int:
			if idx == len(nums):
				return 0
			pos_idx = 1 if is_pos else 0
			if dp[pos_idx][idx] != -1:
				return dp[pos_idx][idx]
			curr = nums[idx] if is_pos else -nums[idx]
			choose = curr + dfs(idx + 1, not is_pos)
			skip = dfs(idx + 1, is_pos)
			dp[pos_idx][idx] = max(choose, skip)
			return dp[pos_idx][idx]
		return dfs(0, True)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
	pub fn max_alternating_sum(nums: Vec<i32>) -> i64 {
		fn dfs(nums: &Vec<i32>, idx: usize, is_pos: bool, dp: &mut [Vec<i64>; 2]) -> i64 {
			if idx == nums.len() { return 0; }
			let pos_idx = if is_pos { 1 } else { 0 };
			if dp[pos_idx][idx] != -1 { return dp[pos_idx][idx]; }
			let curr = if is_pos { nums[idx] as i64 } else { -(nums[idx] as i64) };
			let choose = curr + dfs(nums, idx + 1, !is_pos, dp);
			let skip = dfs(nums, idx + 1, is_pos, dp);
			dp[pos_idx][idx] = choose.max(skip);
			dp[pos_idx][idx]
		}
		let n = nums.len();
		let mut dp = [vec![-1; n], vec![-1; n]];
		dfs(&nums, 0, true, &mut dp)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function maxAlternatingSum(nums: number[]): number {
	const dp: number[][] = Array.from({ length: 2 }, () => Array(nums.length).fill(-1));
	function dfs(idx: number, isPos: boolean): number {
		if (idx === nums.length) return 0;
		const posIdx = isPos ? 1 : 0;
		if (dp[posIdx][idx] !== -1) return dp[posIdx][idx];
		const curr = isPos ? nums[idx] : -nums[idx];
		const choose = curr + dfs(idx + 1, !isPos);
		const skip = dfs(idx + 1, isPos);
		dp[posIdx][idx] = Math.max(choose, skip);
		return dp[posIdx][idx];
	}
	return dfs(0, true);
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each subproblem is solved once.
  • 🧺 Space complexity: O(n), for the DP table and recursion stack.

Method 3 - Bottom up DP - Memoization to Tabulation

Intuition

Convert the recursive DP with memoization into a bottom-up tabulation. Track two states for each index: the best sum if the current index is even (add) or odd (subtract).

Approach

Iterate through the array, maintaining two DP arrays: one for even positions (add) and one for odd positions (subtract). At each step, update both states based on previous values and the current number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
	long long maxAlternatingSum(vector<int>& nums) {
		int n = nums.size();
		vector<long long> even(n), odd(n);
		even[0] = nums[0];
		odd[0] = 0;
		for (int i = 1; i < n; ++i) {
			even[i] = max(even[i - 1], odd[i - 1] + nums[i]);
			odd[i] = max(odd[i - 1], even[i - 1] - nums[i]);
		}
		return max(even[n - 1], odd[n - 1]);
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func maxAlternatingSum(nums []int) int64 {
	n := len(nums)
	even := make([]int64, n)
	odd := make([]int64, n)
	even[0] = int64(nums[0])
	odd[0] = 0
	for i := 1; i < n; i++ {
		even[i] = max(even[i-1], odd[i-1]+int64(nums[i]))
		odd[i] = max(odd[i-1], even[i-1]-int64(nums[i]))
	}
	return max(even[n-1], odd[n-1])
}
func max(a, b int64) int64 { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public long maxAlternatingSum(int[] nums) {
	int n = nums.length;
	long[] even = new long[n], odd = new long[n];
	even[0] = nums[0];
	odd[0] = 0;
	for (int i = 1; i < n; i++) {
		even[i] = Math.max(even[i - 1], odd[i - 1] + nums[i]);
		odd[i] = Math.max(odd[i - 1], even[i - 1] - nums[i]);
	}
	return Math.max(even[n - 1], odd[n - 1]);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
	fun maxAlternatingSum(nums: IntArray): Long {
		val n = nums.size
		val even = LongArray(n)
		val odd = LongArray(n)
		even[0] = nums[0].toLong()
		odd[0] = 0L
		for (i in 1 until n) {
			even[i] = maxOf(even[i - 1], odd[i - 1] + nums[i])
			odd[i] = maxOf(odd[i - 1], even[i - 1] - nums[i])
		}
		return maxOf(even[n - 1], odd[n - 1])
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
	def maxAlternatingSum(self, nums: list[int]) -> int:
		n = len(nums)
		even = [0] * n
		odd = [0] * n
		even[0] = nums[0]
		odd[0] = 0
		for i in range(1, n):
			even[i] = max(even[i - 1], odd[i - 1] + nums[i])
			odd[i] = max(odd[i - 1], even[i - 1] - nums[i])
		return max(even[-1], odd[-1])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
	pub fn max_alternating_sum(nums: Vec<i32>) -> i64 {
		let n = nums.len();
		let mut even = vec![0i64; n];
		let mut odd = vec![0i64; n];
		even[0] = nums[0] as i64;
		odd[0] = 0;
		for i in 1..n {
			even[i] = even[i - 1].max(odd[i - 1] + nums[i] as i64);
			odd[i] = odd[i - 1].max(even[i - 1] - nums[i] as i64);
		}
		even[n - 1].max(odd[n - 1])
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each state is updated once per element.
  • 🧺 Space complexity: O(n), for the DP arrays.

Method 4 - O(1) Bottom up DP

Intuition

Optimize the bottom-up DP by only keeping track of the previous even and odd states, reducing space complexity to O(1).

Approach

Iterate through the array, updating two variables: even (maximum sum ending with an even index) and odd (maximum sum ending with an odd index). At each step, update both based on the current value and previous states.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
	long long maxAlternatingSum(vector<int>& nums) {
		long long even = 0, odd = 0;
		for (int a : nums) {
			long long new_even = max(even, odd + a);
			long long new_odd = new_even - a;
			even = new_even;
			odd = new_odd;
		}
		return even;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func maxAlternatingSum(nums []int) int64 {
	even, odd := int64(0), int64(0)
	for _, a := range nums {
		new_even := max(even, odd+int64(a))
		new_odd := new_even - int64(a)
		even, odd = new_even, new_odd
	}
	return even
}
func max(a, b int64) int64 { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public long maxAlternatingSum(int[] nums) {
	long even = 0, odd = 0;
	for (int a : nums) {
		long new_even = Math.max(even, odd + a);
		long new_odd = new_even - a;
		even = new_even;
		odd = new_odd;
	}
	return even;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	fun maxAlternatingSum(nums: IntArray): Long {
		var even = 0L
		var odd = 0L
		for (a in nums) {
			val new_even = maxOf(even, odd + a)
			val new_odd = new_even - a
			even = new_even
			odd = new_odd
		}
		return even
	}
}
1
2
3
4
5
6
7
8

class Solution:
	def maxAlternatingSum(self, nums: list[int]) -> int:
		even, odd = 0, 0
		for a in nums:
			new_even = max(even, odd + a)
			new_odd = new_even - a
			even, odd = new_even, new_odd
		return even
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
	pub fn max_alternating_sum(nums: Vec<i32>) -> i64 {
		let (mut even, mut odd) = (0i64, 0i64);
		for &a in &nums {
			let new_even = even.max(odd + a as i64);
			let new_odd = new_even - a as i64;
			even = new_even;
			odd = new_odd;
		}
		even
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function maxAlternatingSum(nums: number[]): number {
	let even = 0, odd = 0;
	for (const a of nums) {
		const new_even = Math.max(even, odd + a);
		const new_odd = new_even - a;
		even = new_even;
		odd = new_odd;
	}
	return even;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each element is processed once.
  • 🧺 Space complexity: O(1), only two variables are used.

Method 5 - Using Best Time to Buy and Sell Stock 2

Intuition

This method is inspired by the classic Best Time to Buy and Sell Stock II problem. The idea is to treat each increase in the array as a buy-sell opportunity, accumulating all positive differences between consecutive elements. This approach efficiently computes the maximum alternating sum by summing all upward movements, just like maximizing profit in stock trading.

Approach

Iterate through the array, and for each consecutive pair, add the positive difference to the result. This accumulates the maximum possible alternating sum by treating every increase as a buy-sell opportunity.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
	long long maxAlternatingSum(vector<int>& nums) {
		long long res = nums[0];
		for (int i = 1; i < nums.size(); ++i)
			res += max(nums[i] - nums[i-1], 0);
		return res;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func maxAlternatingSum(nums []int) int64 {
	res := int64(nums[0])
	for i := 1; i < len(nums); i++ {
		diff := nums[i] - nums[i-1]
		if diff > 0 {
			res += int64(diff)
		}
	}
	return res
}
1
2
3
4
5
6

public long maxAlternatingSum(int[] nums) {
	long res = nums[0];
	for (int i = 1; i < nums.length; ++i)
		res += Math.max(nums[i] - nums[i-1], 0);
	return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	fun maxAlternatingSum(nums: IntArray): Long {
		var res = nums[0].toLong()
		for (i in 1 until nums.size) {
			val diff = nums[i] - nums[i-1]
			if (diff > 0) res += diff
		}
		return res
	}
}
1
2
3
4
5
6
7
8

class Solution:
	def maxAlternatingSum(self, nums: list[int]) -> int:
		res = nums[0]
		for i in range(1, len(nums)):
			diff = nums[i] - nums[i-1]
			if diff > 0:
				res += diff
		return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
	pub fn max_alternating_sum(nums: Vec<i32>) -> i64 {
		let mut res = nums[0] as i64;
		for i in 1..nums.len() {
			let diff = nums[i] - nums[i-1];
			if diff > 0 {
				res += diff as i64;
			}
		}
		res
	}
}
1
2
3
4
5
6
7
8

function maxAlternatingSum(nums: number[]): number {
	let res = nums[0];
	for (let i = 1; i < nums.length; i++) {
		const diff = nums[i] - nums[i-1];
		if (diff > 0) res += diff;
	}
	return res;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each element is processed once.
  • 🧺 Space complexity: O(1), only a few variables are used.