企业官网建设流程全解析

LeetCode 1911 最大交替子序列和（Maximum Alternating Subsequence Sum）四种解法全解析：从递归到状态机 DP

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文基于当前仓库 articles/maximum-alternating-subsequence-sum.md 的完整题解，深入讲解 LeetCode 1911「最大交替子序列和」问题：子序列中元素按"先加、后减、再加、再减"的交替方式求和，求可达到的最大值。读完本文，你将掌握从暴力递归、记忆化搜索、自底向上 DP 到 O(1) 空间的滚动变量状态机 DP 的完整进化路径，并能对照仓库中 C++ 与 Kotlin 的实现，在面试中快速写出任意一种正确解。

问题定义与核心概念

给定一个整数数组nums，返回其任意子序列的最大交替和。对于一个 0 索引数组，交替和定义为偶数索引元素之和减去奇数索引元素之和，例如[4, 2, 5, 3]的交替和为(4 + 5) - (2 + 3) = 4。注意这里的位置编号指的是所选子序列内部的位置，而不是原数组的下标。

以仓库 cpp/1911-maximum-alternating-subsequence-sum.cpp 注释中的示例说明：设nums = [6, 2, 1, 2, 4, 5]，选择子序列{6, 1, 5}，其交替和为(6 + 5) - 1 = 10，即为最优解，因此返回10。

做这道题之前，建议先掌握以下三项前置知识：

• 递归（Recursion）：将大问题拆解为带基准情形（base case）与递归情形（recursive case）的子问题；
• 动态规划（Dynamic Programming）：识别重叠子问题，使用记忆化（memoization）避免重复计算；
• 状态机 DP（State Machine DP）：跟踪多个状态（偶数位/奇数位），并在状态间做最优转移。

方案一：递归（Recursion）

直觉

交替子序列和在偶数位加、奇数位减。在每个下标处有两个选择：把当前元素纳入子序列，或跳过它。若纳入，其符号取决于它在所选子序列中的位置是偶数位还是奇数位。递归方法在每个下标处都探索这两种选择，并跟踪"下一个被选中的元素将落在偶数位还是奇数位"。

算法步骤

1. 定义dfs(i, even)，其中i是当前下标，even表示下一个被选取的元素是否贡献正值；
2. 基准情形：当i == n时返回0；
3. 若even为真，则要么选取nums[i]（累加它）并以even = false递归，要么跳过并以even = true递归；
4. 若even为假，则要么选取nums[i]（累减它）并以even = true递归，要么跳过并以even = false递归；
5. 返回"选取"与"跳过"两者中的较大值；
6. 从dfs(0, true)开始。

多语言实现

Python：

class Solution: def maxAlternatingSum(self, nums: List[int]) -> int: def dfs(i, even): if i == len(nums): return 0 total = nums[i] if even else -nums[i] return max(total + dfs(i + 1, not even), dfs(i + 1, even)) return dfs(0, True)

Java：

public class Solution { public long maxAlternatingSum(int[] nums) { return dfs(nums, 0, true); } private long dfs(int[] nums, int i, boolean even) { if (i == nums.length) { return 0; } long total = even ? nums[i] : -nums[i]; return Math.max(total + dfs(nums, i + 1, !even), dfs(nums, i + 1, even)); } }

C++：

class Solution { public: long long maxAlternatingSum(vector<int>& nums) { return dfs(nums, 0, true); } private: long long dfs(vector<int>& nums, int i, bool even) { if (i == nums.size()) { return 0; } long long total = even ? nums[i] : -nums[i]; return max(total + dfs(nums, i + 1, !even), dfs(nums, i + 1, even)); } };

JavaScript：

class Solution { /** * @param {number[]} nums * @return {number} */ maxAlternatingSum(nums) { const dfs = (i, even) => { if (i === nums.length) { return 0; } const total = even ? nums[i] : -nums[i]; return Math.max(total + dfs(i + 1, !even), dfs(i + 1, even)); }; return dfs(0, true); } }

Go：

func maxAlternatingSum(nums []int) int64 { var dfs func(i int, even bool) int64 dfs = func(i int, even bool) int64 { if i == len(nums) { return 0 } var total int64 if even { total = int64(nums[i]) } else { total = -int64(nums[i]) } return max64(total+dfs(i+1, !even), dfs(i+1, even)) } return dfs(0, true) } func max64(a, b int64) int64 { if a > b { return a } return b }

Kotlin：

class Solution { fun maxAlternatingSum(nums: IntArray): Long { fun dfs(i: Int, even: Boolean): Long { if (i == nums.size) return 0L val total = if (even) nums[i].toLong() else -nums[i].toLong() return maxOf(total + dfs(i + 1, !even), dfs(i + 1, even)) } return dfs(0, true) } }

Swift：

class Solution { func maxAlternatingSum(_ nums: [Int]) -> Int { func dfs(_ i: Int, _ even: Bool) -> Int { if i == nums.count { return 0 } let total = even ? nums[i] : -nums[i] return max(total + dfs(i + 1, !even), dfs(i + 1, even)) } return dfs(0, true) } }

Rust：

impl Solution { pub fn max_alternating_sum(nums: Vec<i32>) -> i64 { fn dfs(i: usize, even: bool, nums: &[i32]) -> i64 { if i == nums.len() { return 0; } let total = if even { nums[i] as i64 } else { -(nums[i] as i64) }; (total + dfs(i + 1, !even, nums)).max(dfs(i + 1, even, nums)) } dfs(0, true, &nums) } }

复杂度

• 时间复杂度：$O(2 ^ n)$
• 空间复杂度：$O(n)$（递归栈深度）

每个下标处都分叉出"选取/跳过"两条路径，因此状态树呈指数级增长，仅适用于理解思路，无法通过大数据量测试。

方案二：动态规划（自顶向下 / Top-Down）

直觉

递归解法存在大量重叠子问题：状态(i, even)可能通过多条不同路径被反复到达，因此可以缓存结果来避免重复计算。由于共有n个下标和2种奇偶状态，总共只有O(n)个唯一状态。对它们做记忆化，就能把指数级时间复杂度降为线性。

算法步骤

1. 创建记忆化表dp[i][even]，初始化为-1（表示未访问）；
2. 按之前的逻辑定义dfs(i, even)；
3. 计算前先检查dp[i][even]是否已缓存，命中则直接返回；
4. 计算完成后把结果存入dp[i][even]；
5. 返回dfs(0, 1)，其中1代表偶数位状态。

多语言实现

Python：

class Solution: def maxAlternatingSum(self, nums: List[int]) -> int: dp = {} def dfs(i, even): if i == len(nums): return 0 if (i, even) in dp: return dp[(i, even)] total = nums[i] if even else -nums[i] dp[(i, even)] = max(total + dfs(i + 1, not even), dfs(i + 1, even)) return dp[(i, even)] return dfs(0, True)

Java：

public class Solution { private long dp[][]; public long maxAlternatingSum(int[] nums) { int n = nums.length; dp = new long[n][2]; for (int i = 0; i < n; i++) { dp[i][0] = -1; dp[i][1] = -1; } return dfs(nums, 0, 1); } private long dfs(int[] nums, int i, int even) { if (i == nums.length) { return 0; } if (dp[i][even] != -1) { return dp[i][even]; } long total = even == 1 ? nums[i] : -nums[i]; dp[i][even] = Math.max(total + dfs(nums, i + 1, 1 - even), dfs(nums, i + 1, even)); return dp[i][even]; } }

C++：

class Solution { vector<vector<long long>> dp; public: long long maxAlternatingSum(vector<int>& nums) { dp.assign(nums.size(), vector<long long>(2, -1)); return dfs(nums, 0, true); } private: long long dfs(vector<int>& nums, int i, bool even) { if (i == nums.size()) { return 0; } if (dp[i][even] != -1) { return dp[i][even]; } long long total = even ? nums[i] : -nums[i]; dp[i][even] = max(total + dfs(nums, i + 1, !even), dfs(nums, i + 1, even)); return dp[i][even]; } };

JavaScript：

class Solution { /** * @param {number[]} nums * @return {number} */ maxAlternatingSum(nums) { const n = nums.length; const dp = Array.from({ length: n }, () => Array(2).fill(-1)); const dfs = (i, even) => { if (i === n) { return 0; } if (dp[i][even] !== -1) { return dp[i][even]; } const total = even === 1 ? nums[i] : -nums[i]; dp[i][even] = Math.max( total + dfs(i + 1, 1 - even), dfs(i + 1, even), ); return dp[i][even]; }; return dfs(0, 1); } }

Go：

func maxAlternatingSum(nums []int) int64 { n := len(nums) dp := make([][]int64, n) for i := range dp { dp[i] = []int64{-1, -1} } var dfs func(i, even int) int64 dfs = func(i, even int) int64 { if i == n { return 0 } if dp[i][even] != -1 { return dp[i][even] } var total int64 if even == 1 { total = int64(nums[i]) } else { total = -int64(nums[i]) } dp[i][even] = max64(total+dfs(i+1, 1-even), dfs(i+1, even)) return dp[i][even] } return dfs(0, 1) } func max64(a, b int64) int64 { if a > b { return a } return b }

Kotlin：

class Solution { fun maxAlternatingSum(nums: IntArray): Long { val n = nums.size val dp = Array(n) { LongArray(2) { -1L } } fun dfs(i: Int, even: Int): Long { if (i == n) return 0L if (dp[i][even] != -1L) return dp[i][even] val total = if (even == 1) nums[i].toLong() else -nums[i].toLong() dp[i][even] = maxOf(total + dfs(i + 1, 1 - even), dfs(i + 1, even)) return dp[i][even] } return dfs(0, 1) } }

Swift：

class Solution { func maxAlternatingSum(_ nums: [Int]) -> Int { let n = nums.count var dp = [[Int]](repeating: [-1, -1], count: n) func dfs(_ i: Int, _ even: Int) -> Int { if i == n { return 0 } if dp[i][even] != -1 { return dp[i][even] } let total = even == 1 ? nums[i] : -nums[i] dp[i][even] = max(total + dfs(i + 1, 1 - even), dfs(i + 1, even)) return dp[i][even] } return dfs(0, 1) } }

Rust：

impl Solution { pub fn max_alternating_sum(nums: Vec<i32>) -> i64 { let n = nums.len(); let mut dp = vec![[-1i64; 2]; n]; fn dfs(i: usize, even: usize, nums: &[i32], dp: &mut Vec<[i64; 2]>) -> i64 { if i == nums.len() { return 0; } if dp[i][even] != -1 { return dp[i][even]; } let total = if even == 1 { nums[i] as i64 } else { -(nums[i] as i64) }; dp[i][even] = (total + dfs(i + 1, 1 - even, nums, dp)) .max(dfs(i + 1, even, nums, dp)); dp[i][even] } dfs(0, 1, &nums, &mut dp) } }

仓库中的 kotlin/1911-maximum-alternating-subsequence-sum.kt 正是这种自顶向下记忆化的实现：它使用Array(2) { LongArray(nums.size) { -1L } }作为记忆表，dp[even][i]表示"下一个选中元素处于 even 奇偶状态下、从下标 i 开始的最大交替和"，命中缓存直接返回，未命中则计算"选取（取反奇偶）"与"跳过（保持奇偶）"的较大值。可见记忆化不仅可以写成dp[i][even]，也可以写成dp[even][i]，两种索引顺序等价。

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

方案三：动态规划（自底向上 / Bottom-Up）

直觉

可以把自顶向下改成自底向上，迭代地填充 DP 表。对每个位置跟踪两个值：下一个被选元素落在偶数位时的最大交替和，以及落在奇数位时的最大交替和。从数组末尾向前递推，在每个位置根据"选取或跳过"两种选择计算这两个值。

算法步骤

1. 创建二维数组dp[n+1][2]，全部初始化为0；
2. 从i = n-1倒序迭代到0：
   • dp[i][1]（偶数位）= max(选取nums[i]加上dp[i+1][0]，跳过保持dp[i+1][1])；
   • dp[i][0]（奇数位）= max(选取-nums[i]加上dp[i+1][1]，跳过保持dp[i+1][0])；
3. 返回dp[0][1]，因为我们一开始期待选取偶数位元素。

多语言实现

Python：

class Solution: def maxAlternatingSum(self, nums: List[int]) -> int: n = len(nums) dp = [[0] * 2 for _ in range(n + 1)] # dp[i][0] -> odd, dp[i][1] -> even for i in range(n - 1, -1, -1): dp[i][1] = max(nums[i] + dp[i + 1][0], dp[i + 1][1]) # even dp[i][0] = max(-nums[i] + dp[i + 1][1], dp[i + 1][0]) # odd return dp[0][1]

Java：

public class Solution { public long maxAlternatingSum(int[] nums) { int n = nums.length; long[][] dp = new long[n + 1][2]; // dp[i][0] -> odd, dp[i][1] -> even for (int i = n - 1; i >= 0; i--) { dp[i][1] = Math.max(nums[i] + dp[i + 1][0], dp[i + 1][1]); // even dp[i][0] = Math.max(-nums[i] + dp[i + 1][1], dp[i + 1][0]); // odd } return dp[0][1]; } }

C++：

class Solution { public: long long maxAlternatingSum(vector<int>& nums) { int n = nums.size(); vector<vector<long long>> dp(n + 1, vector<long long>(2, 0)); // dp[i][0] -> odd, dp[i][1] -> even for (int i = n - 1; i >= 0; i--) { dp[i][1] = max(nums[i] + dp[i + 1][0], dp[i + 1][1]); // even dp[i][0] = max(-nums[i] + dp[i + 1][1], dp[i + 1][0]); // odd } return dp[0][1]; } };

JavaScript：

class Solution { /** * @param {number[]} nums * @return {number} */ maxAlternatingSum(nums) { const n = nums.length; const dp = Array.from({ length: n + 1 }, () => [0, 0]); // dp[i][0] -> odd, dp[i][1] -> even for (let i = n - 1; i >= 0; i--) { dp[i][1] = Math.max(nums[i] + dp[i + 1][0], dp[i + 1][1]); // even dp[i][0] = Math.max(-nums[i] + dp[i + 1][1], dp[i + 1][0]); // odd } return dp[0][1]; // Result starts with even index } }

Go：

func maxAlternatingSum(nums []int) int64 { n := len(nums) dp := make([][]int64, n+1) for i := range dp { dp[i] = []int64{0, 0} } for i := n - 1; i >= 0; i-- { dp[i][1] = max64(int64(nums[i])+dp[i+1][0], dp[i+1][1]) // even dp[i][0] = max64(-int64(nums[i])+dp[i+1][1], dp[i+1][0]) // odd } return dp[0][1] } func max64(a, b int64) int64 { if a > b { return a } return b }

Kotlin：

class Solution { fun maxAlternatingSum(nums: IntArray): Long { val n = nums.size val dp = Array(n + 1) { LongArray(2) } for (i in n - 1 downTo 0) { dp[i][1] = maxOf(nums[i] + dp[i + 1][0], dp[i + 1][1]) // even dp[i][0] = maxOf(-nums[i] + dp[i + 1][1], dp[i + 1][0]) // odd } return dp[0][1] } }

Swift：

class Solution { func maxAlternatingSum(_ nums: [Int]) -> Int { let n = nums.count var dp = [[Int]](repeating: [0, 0], count: n + 1) for i in stride(from: n - 1, through: 0, by: -1) { dp[i][1] = max(nums[i] + dp[i + 1][0], dp[i + 1][1]) // even dp[i][0] = max(-nums[i] + dp[i + 1][1], dp[i + 1][0]) // odd } return dp[0][1] } }

Rust：

impl Solution { pub fn max_alternating_sum(nums: Vec<i32>) -> i64 { let n = nums.len(); let mut dp = vec![[0i64; 2]; n + 1]; // dp[i][0] -> odd, dp[i][1] -> even for i in (0..n).rev() { dp[i][1] = (nums[i] as i64 + dp[i + 1][0]).max(dp[i + 1][1]); // even dp[i][0] = (-(nums[i] as i64) + dp[i + 1][1]).max(dp[i + 1][0]); // odd } dp[0][1] } }

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

方案四：动态规划（空间优化 / Space Optimized）

直觉

观察状态转移可以发现，每个状态只依赖下一个下标的状态，因此完全不需要整张 DP 表，仅用两个变量即可跟踪"当前下标开始的后缀中，偶数位最佳和"与"奇数位最佳和"。这能把空间从 $O(n)$ 降到 $O(1)$，同时逻辑完全不变。

算法步骤

1. 初始化sumEven = 0、sumOdd = 0；
2. 从i = n-1倒序迭代到0：
   • tmpEven = max(nums[i] + sumOdd, sumEven)，表示下一个选中元素在偶数位时的最优和；
   • tmpOdd = max(-nums[i] + sumEven, sumOdd)，表示下一个选中元素在奇数位时的最优和；
   • 更新sumEven = tmpEven、sumOdd = tmpOdd；
3. 返回sumEven。

多语言实现

Python：

class Solution: def maxAlternatingSum(self, nums: List[int]) -> int: sumEven = sumOdd = 0 for i in range(len(nums) - 1, -1, -1): tmpEven = max(sumOdd + nums[i], sumEven) tmpOdd = max(sumEven - nums[i], sumOdd) sumEven, sumOdd = tmpEven, tmpOdd return sumEven

Java：

public class Solution { public long maxAlternatingSum(int[] nums) { long sumEven = 0, sumOdd = 0; for (int i = nums.length - 1; i >= 0; i--) { long tmpEven = Math.max(nums[i] + sumOdd, sumEven); long tmpOdd = Math.max(-nums[i] + sumEven, sumOdd); sumEven = tmpEven; sumOdd = tmpOdd; } return sumEven; } }

C++：

class Solution { public: long long maxAlternatingSum(vector<int>& nums) { long long sumEven = 0, sumOdd = 0; for (int i = nums.size() - 1; i >= 0; i--) { long long tmpEven = max(nums[i] + sumOdd, sumEven); long long tmpOdd = max(-nums[i] + sumEven, sumOdd); sumEven = tmpEven; sumOdd = tmpOdd; } return sumEven; } };

JavaScript：

class Solution { /** * @param {number[]} nums * @return {number} */ maxAlternatingSum(nums) { let sumEven = 0, sumOdd = 0; for (let i = nums.length - 1; i >= 0; i--) { let tmpEven = Math.max(nums[i] + sumOdd, sumEven); let tmpOdd = Math.max(-nums[i] + sumEven, sumOdd); sumEven = tmpEven; sumOdd = tmpOdd; } return sumEven; } }

Go：

func maxAlternatingSum(nums []int) int64 { var sumEven, sumOdd int64 = 0, 0 for i := len(nums) - 1; i >= 0; i-- { tmpEven := max64(int64(nums[i])+sumOdd, sumEven) tmpOdd := max64(-int64(nums[i])+sumEven, sumOdd) sumEven, sumOdd = tmpEven, tmpOdd } return sumEven } func max64(a, b int64) int64 { if a > b { return a } return b }

Kotlin：

class Solution { fun maxAlternatingSum(nums: IntArray): Long { var sumEven = 0L var sumOdd = 0L for (i in nums.lastIndex downTo 0) { val tmpEven = maxOf(nums[i] + sumOdd, sumEven) val tmpOdd = maxOf(-nums[i] + sumEven, sumOdd) sumEven = tmpEven sumOdd = tmpOdd } return sumEven } }

Swift：

class Solution { func maxAlternatingSum(_ nums: [Int]) -> Int { var sumEven = 0 var sumOdd = 0 for i in stride(from: nums.count - 1, through: 0, by: -1) { let tmpEven = max(nums[i] + sumOdd, sumEven) let tmpOdd = max(-nums[i] + sumEven, sumOdd) sumEven = tmpEven sumOdd = tmpOdd } return sumEven } }

Rust：

impl Solution { pub fn max_alternating_sum(nums: Vec<i32>) -> i64 { let mut sum_even: i64 = 0; let mut sum_odd: i64 = 0; for i in (0..nums.len()).rev() { let tmp_even = (nums[i] as i64 + sum_odd).max(sum_even); let tmp_odd = (-(nums[i] as i64) + sum_even).max(sum_odd); sum_even = tmp_even; sum_odd = tmp_odd; } sum_even } }

仓库中的 cpp/1911-maximum-alternating-subsequence-sum.cpp 采用的正是这一终极形态：仅用long long even, odd, tmpEven, tmpOdd四个局部变量完成全部计算，代码注释中标明其复杂度为Time: O(n)、Space: O(1)，与该方案完全一致。这也是面试中最推荐的写法——既正确又省内存，且不易写错。

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$ 额外空间

常见陷阱（Common Pitfalls）

混淆子序列与子数组

子序列（subsequence）不要求元素在原数组中连续，而子数组（subarray）必须连续。本题可以自由跳过元素。例如从[4, 2, 5, 3]中可以选取[4, 2, 5]（下标 0、1、2），也可以选取[4, 5]（下标 0、2）。若把本题误当作子数组问题处理，就会得出错误答案。上述所有 DP 方案中"跳过当前元素并保持奇偶状态不变"的分支，正是子序列允许跳过的数学体现。

误解交替规律

交替和从第一个被选元素开始做加法，第二个被选元素做减法，第三个再加，依此类推。这个"加减交替"规律取决于所选子序列内部的位置，而非原数组下标。如果从减法开始，或数错奇偶位，结果就会出错。注意本文所有方案都以even = true/dp[0][1]起步，强制第一个选中元素为正号。

整数溢出

当数组较大且元素值高达 $10^5$ 时，和可能超过 32 位整数上限。因此 Java/C++ 实现一律使用long/long long返回值类型，Go/Rust 使用int64，Kotlin 使用Long，以保证大数据用例下不溢出。如果忽略这一点，较大的测试用例就会出现溢出错误。这也是 cpp/1911-maximum-alternating-subsequence-sum.cpp 与 kotlin/1911-maximum-alternating-subsequence-sum.kt 都显式选用 64 位整型的原因。

总结：四层递进路线

这四种方案本质上是同一套状态机 DP 的不同实现：状态为"下一个选中元素落在偶数位/奇数位"，转移为"选取（翻转奇偶）或跳过（保持奇偶）"。掌握这一模式后，类似的交替类 DP 题目（如股票买卖系列）都可以套用同样的状态机思路。仓库 README.md 收录了本问题对应的 C++ 与 Kotlin 解法，配合本文 articles/maximum-alternating-subsequence-sum.md 的完整推导，即可完成从入门到优化的全部练习。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode