最大交替子序列和 图解题解

交替和的加减号，到底跟着哪个下标走

给数组 nums，挑一个子序列（按原顺序跳着选），重新从 0 编号，偶数位相加、奇数位相减叫交替和，求最大值。加减号跟重编号后的位置走：[6,2,1,2,5] 里挑 [6,1,5]，1 原来排第 2 位（原数组也从 0 数），重编号后落到第 1 位成了减项，(6+5)-1=10，与示例二一致。

子序列有 2ⁿ 条，挨条算交替和为什么走不通

每个数选或不选，n 个数就是 2ⁿ 条子序列，几十个数就数不完。而且前面一段怎么选最好，在后面每条分支里被重算，这份成绩不随后面的数改变，存下来复用就是动态规划（本题存「加项或减项收尾」两行成绩，后面的数直接在表上接）。

为什么一行状态记不住，非得拆成 f、g 两行

只记「前 i 个数的最大交替和」推不下去：下一个数该加该减，取决于已选的最后一个是加项还是减项。于是把状态（描述算到哪一步的那组量）按收尾拆成两行：g[i] 记前 i 个数里加项收尾的最大交替和，f[i] 记减项收尾的最大。空前缀 f[0]=g[0]=0 代表一个数都没选，第一个数走 f[0]+x 就能进场当加项。

想让加项进场，为什么必须从 f 行接过来

转移（由上一列推出这一列的式子）每行两条来路：想让当前数 x 当加项，前一个被选的数必须是减项，所以 g[i]=max(f[i-1]+x, g[i-1])，后一项是不选、照抄左边；f 行对称，f[i]=max(g[i-1]-x, f[i-1])。加号行的来源在减号行、反过来也一样，「交替」说的就是这件事。减一个数当下变小，这笔亏存在 f 行里，等大数出现接回加号行就赚回来。

拿示例 [6,2,1,2,5] 把两行表逐列填一遍

f[0]=g[0]=0。来 6：g[1]=max(0+6,0)=6，f[1]=max(0-6,0)=0。来 2：g[2]=max(0+2,6)=6，f[2]=max(6-2,0)=4。来 1：g[3]=max(4+1,6)=6，f[3]=max(6-1,4)=5。来 2：g[4]=max(5+2,6)=7，f[4]=max(6-2,5)=5。来 5：g[5]=max(5+5,7)=10，f[5]=max(7-5,5)=5。

答案 max(f[5],g[5])=10，和示例二对上。倒着追：g[5]=f[4]+5，f[4] 照抄 f[3]，f[3]=g[2]-1，g[2] 照抄 g[1]，即加 6、减 1、加 5，正是子序列 [6,1,5]。

Java 用 int 存交替和，为什么会悄悄得出负数

一遍循环、每个数两次取较大，时间 O(n)（操作次数随数组长度线性涨）；两个 n+1 长的数组占 O(n)，每列只靠上一列，换成两个滚动变量（只留最新一列）可压到 O(1)。交替和能累到十的十次方量级（n 和每个数都能到十万，十万×十万），超出 Java int 约 2.1×10⁹ 的上限就变负数，得用 long，C++ 用 long long，Python 不受限。边界：单个数就返回它本身（g[1] 把它当加项收下）；收尾取 f[n]、g[n] 较大者，本题全是正数、g[n] 不低于 f[n]，只回 g[n] 碰巧也对，按 max 写最稳。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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])

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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]);
    }
};

Java

import java.util.*;
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]);
    }
}