What is the pattern used to solve the Maximum Alternating Subsequence Sum?

The pattern used is dynamic programming with state transitions to track alternating sums for both even and odd indexed subsequences.

How do you track the alternating sum in this problem?

You track the sum by maintaining two variables—one for even indices and one for odd indices—and iterating through the array to update them accordingly.

What is the time complexity of the Maximum Alternating Subsequence Sum problem?

The time complexity is O(n) because the solution requires a single traversal through the array.

How does GhostInterview assist in solving the Maximum Alternating Subsequence Sum problem?

GhostInterview provides an interactive solver to help you implement dynamic programming and optimize the solution step-by-step.

Are there any edge cases in the Maximum Alternating Subsequence Sum problem?

Yes, edge cases such as arrays with only one element or very small arrays should be handled appropriately.

#1911

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最大交替子序列和

一个下标从 0 开始的数组的交替和定义为偶数下标处元素之和减去奇数下标处元素之和。比方说，数组 [4,2,5,3] 的交替和为 (4 + 5) - (2 + 3) = 4 。给你一个数组 nums ，请你返回 nums 中任意子序列的最大交替和（子序列的下标重新从 0…

数组动态规划

题目描述

一个下标从 0 开始的数组的 交替和 定义为偶数下标处元素之和减去奇数下标处元素之和。

比方说，数组 [4,2,5,3] 的交替和为 (4 + 5) - (2 + 3) = 4 。

给你一个数组 nums ，请你返回 nums 中任意子序列的 最大交替和 （子序列的下标重新从 0 开始编号）。

一个数组的 子序列 是从原数组中删除一些元素后（也可能一个也不删除）剩余元素不改变顺序组成的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的一个子序列（加粗元素），但是 [2,4,2] 不是。

示例 1：

输入：nums = [4,2,5,3]
输出：7
解释：最优子序列为 [4,2,5] ，交替和为 (4 + 5) - 2 = 7 。

示例 2：

输入：nums = [5,6,7,8]
输出：8
解释：最优子序列为 [8] ，交替和为 8 。

示例 3：

输入：nums = [6,2,1,2,4,5]
输出：10
解释：最优子序列为 [6,1,5] ，交替和为 (6 + 5) - 1 = 10 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示从前 $i$ 个元素中选出的子序列，且最后一个元素为奇数下标时的最大交替和，定义 $g[i]$ 表示从前 $i$ 个元素中选出的子序列，且最后一个元素为偶数下标时的最大交替和。初始时 $f[0] = g[0] = 0$ 。答案为 $max(f[n], g[n])$ 。

我们考虑第 $i$ 个元素 $nums[i - 1]$ ：

如果选取该元素且该元素为奇数下标，那么上一个元素必须为偶数下标，且只能从前 $i-1$ 个元素中选取，因此 $f[i] = g[i - 1] - nums[i - 1]$ ；如果不选取该元素，那么 $f[i] = f[i - 1]$ 。

同理，如果选取该元素且该元素为偶数下标，那么上一个元素必须为奇数下标，且只能从前 $i-1$ 个元素中选取，因此 $g[i] = f[i - 1] + nums[i - 1]$ ；如果不选取该元素，那么 $g[i] = g[i - 1]$ 。

综上，我们可以得到状态转移方程：

\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}

最终答案为 $max(f[n], g[n])$ 。

我们注意到 $f[i]$ 和 $g[i]$ 只与 $f[i - 1]$ 和 $g[i - 1]$ 有关，因此我们可以使用两个变量代替数组，将空间复杂度降低到 $O(1)$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

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])

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the ability to optimize both time and space complexity in dynamic programming solutions.
question_mark
Assess the candidate's understanding of alternating sum and how dynamic programming applies.
question_mark
Check whether the candidate can correctly handle the state transitions between even and odd indexed subsequences.

warning

常见陷阱

外企场景

error
Misunderstanding the alternating sum definition, which may lead to incorrect subsequences.
error
Failing to optimize space by using unnecessary arrays for each possible subsequence.
error
Not handling edge cases, such as very small arrays or arrays with only one element.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider the scenario where the input array contains a single element.
arrow_right_alt
Explore the impact of large input sizes on performance and how to optimize for such cases.
arrow_right_alt
Challenge the candidate with an extension that requires finding the subsequence with the maximum alternating sum while also considering additional constraints.

help

常见问题

外企场景

继续练习

#1928 规定时间内到达终点的最小花费 #1937 扣分后的最大得分 #1883 准时抵达会议现场的最小跳过休息次数