1911. 最大交替子序列和

发表于 2025-12-08 分类于力扣阅读次数： Waline：本文字数： 734 阅读时长 ≈ 2 分钟

考点

状态机DP

思路

一、题目核心

给定数组： \[ nums = [a_1, a_2, \dots, a_n] \] 从中选择一个子序列，使其交替和最大： \[ a_{i_1} - a_{i_2} + a_{i_3} - a_{i_4} + \dots \] 要求最大值。

二、状态定义（核心）

定义二维 DP： \[ f[i][0] = \text{考虑前 } i \text{ 个数，最后一个被选中的数是 } + \text{ 号时的最大值} \] 也就是说：

0 表示当前状态最后一次是加号
1 表示当前状态最后一次是减号

三、初始值为什么这样设

只考虑第 0 个元素： \[ f[0][0] = nums[0] \] 因为只选一个数时，必然是正号。 \[ f[0][1] = -\infty \] 因为：

不可能只选一个数就出现减号
此状态是 非法状态
实现中用：

1	f[0][1] = INT_MIN;

作为负无穷。

四、状态转移方程

对每个新元素 nums[i]，有两类决策：

✅ 不选 nums[i] → 状态继承
✅ 选 nums[i] → 发生符号切换

1️⃣ 计算减号状态 `f[i][1]`

只有两种来源：

不选当前数：

\[ f[i][1] = f[i-1][1] \]

当前数作为减号：

\[ f[i-1][0] - nums[i] \]

最终转移为： \[ f[i][1] = \max\left(f[i-1][1],\; f[i-1][0] - nums[i]\right) \] 对应代码：

1	f[i][1] = max(f[i - 1][1], f[i - 1][0] - nums[i]);

2️⃣ 计算加号状态 `f[i][0]`

同样两类来源：

不选当前数：

\[ f[i][0] = f[i-1][0] \]

当前数作为加号：

如果之前是负号：

\[ f[i-1][1] + nums[i] \]

如果之前是非法负无穷，允许“重开子序列”：

\[ nums[i] = 0 + nums[i] \]

合并为： \[ \max(0,\; f[i-1][1]) + nums[i] \] 最终转移为： \[ f[i][0] = \max\left(f[i-1][0],\; \max(0, f[i-1][1]) + nums[i]\right) \] 对应代码：

1	f[i][0] = max(f[i - 1][0], max(0LL, f[i - 1][1]) + nums[i]);

五、代码

class Solution {
public:
    static const int maxn = 1e5 + 5;
    long long maxAlternatingSum(vector<int>& nums) {
        long long f[maxn][2];
        f[0][0] = nums[0];
        f[0][1] = INT_MIN;   // 负无穷：初始不可能是减号

        for (int i = 1; i < nums.size(); ++i) {
            // 计算减号状态
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - nums[i]);

            // 计算加号状态
            f[i][0] = max(
                f[i - 1][0],
                max(0LL, f[i - 1][1]) + nums[i]
            );
        }

        return max(f[nums.size() - 1][0], f[nums.size() - 1][1]);
    }
};

当然也可以滚动数组：

class Solution {
public:
    static const int maxn = 1e5 + 5;
    long long maxAlternatingSum(vector<int>& nums) {
        long long a = nums[0], b = INT_MIN;
        for (int i = 1; i < nums.size(); ++i) {
            long long ta, tb;
            tb = max(b, a - nums[i]), ta = max(a, max(0LL, b) + nums[i]);
            a = ta, b = tb;
        }
        return max(a, b);
    }
};

六、为什么可以用 `max(0, f[i-1][1])`

这是一个非常关键的合法性技巧：

当 f[i-1][1] < 0，说明：
- 不如直接从 nums[i] 重新开始
当 f[i-1][1] ≥ 0：
- 说明可以自然接在负号后面加

等价于： \[ \max(nums[i],\; f[i-1][1] + nums[i]) \]

七、最终答案

最终结果在两种状态中产生： \[ \max\left(f[n-1][0],\; f[n-1][1]\right) \] 因为最后一个符号可能是 +，也可能是 -。

考点

思路