NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 27 题

（双子序列最大和）给定一个长度为 $n(3 \leq n \leq 1000)$ 的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求：每个连续子序列长度至少为 $1$，且两个连续子序列之间至少间隔 $1$ 个数。（第五空 $4$ 分，其余 $2.5$ 分）

#include <iostream> 
using namespace std;  
const int MAXN = 1000; 
int n, i, ans, sum; 
int x[MAXN]; 
int lmax[MAXN]; // lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中，最大的序列和 
int rmax[MAXN]; // rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中，最大的序列和 
int main() { 
    cin >> n; 
    for (i = 0; i < n; i++) 
        cin >> x[i]; 
    lmax[0] = x[0]; 
    for (i = 1; i < n; i++) 
        if (lmax[i - 1] <= 0) 
            lmax[i] = x[i]; 
        else 
            lmax[i] = lmax[i - 1] + x[i]; 
    for (i = 1; i < n; i++) 
        if (lmax[i] < lmax[i - 1]) 
            lmax[i] = lmax[i - 1]; 
        (1)    ; 
    for (i = n - 2; i >= 0; i--) 
        if (rmax[i + 1] <= 0) 
                (2)    ; 
        else 
          

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这道题本质是求两个不相交连续子数组的最大和。拿到题先别急着填空，想清楚：lmax 是左边的最大后缀和，rmax 是右边的最大前缀和。中间那个‘间隔至少1个数’的约束，直接把两个子数组的取值范围锁死了——左子数组只能取到 i-1，右子数组只能从 i+1 开始。所以遍历中间点 i，把 lmax[i-1] 和 rmax[i+1] 加起来，取最大值就是答案。代码里那些 if-else 其实就是动态规划里的‘继承最大值’逻辑，填对它们，后面直接套公式就能过。

最容易栽跟头的地方有两处：一是把 rmax 的初始化写错，以为所有 rmax 都是 0 或者直接从 x[i] 开始累加，结果第一个空漏了 rmax[n-1]=x[n-1]，导致后面递推全错；二是理解错‘间隔至少1个数’的含义，以为只要两个子数组不重叠就行，结果把 lmax[i] 和 rmax[i] 直接相加，忽略了中间必须留空位的限制，这样算出来的和往往偏大，遇到全正数序列时尤其危险。另外，动态规划里那个‘如果前一个值小于当前值就继承前一个’的逻辑，很多学生会写成直接赋值，忘记取 max，导致 rmax 数组里存的是局部最大值而不是全局后缀最大值，最后答案自然不对。

这道题考查的是动态规划中的‘最大子段和’变体，核心在于处理两个不相交且中间至少隔一个元素的连续子序列。命题人喜欢在细节上挖坑：一是‘间隔至少1个数’这个约束，二是动态规划数组的初始化与递推逻辑。很多学生一看到‘最大和’就想到 Kadane 算法，但这里有两个子数组，且不能相邻，所以必须引入两个辅助数组 lmax 和 rmax，分别记录以每个位置结尾的最大左子段和、以每个位置开头的最大右子段和。这样，对于任意中间分隔点 i（i 从 1 到 n-2），左子段最远能到 i-1，右子段最近从 i+1 开始，两者自然不相交且中间至少隔一个数，完美契合题意。因此，答案就是遍历所有可能的 i，计算 lmax[i-1] + rmax[i+1] 的最大值。代码里前两段循环就是在预处理 lmax 和 rmax，后一段循环就是枚举分隔点求和。现在逐空分析。第一个空在 lmax 的预处理结束后，目的是保证 lmax 数组是单调不减的：如果 lmax[i] 比 lmax[i-1] 小，说明以 i 结尾的最大子段和不如以 i-1 结尾的大，那我们可以直接把 lmax[i] 更新为 lmax[i-1]，这样后续取最大值时就不会漏掉更大的值。所以 (1) 填的是 if (lmax[i] < lmax[i - 1]) lmax[i] = lmax[i - 1];。第二个空在 rmax 的初始化部分，rmax[i] 定义为包含 x[i] 及其右侧的最大子段和。对于最后一个元素 x[n-1]，它右侧没有元素，所以 rmax[n-1] 只能等于 x[n-1]，这就是 (2) 填 rmax[n-1] = x[n-1] 的原因。第三个空是 rmax 的递推：从右往左扫描，如果 rmax[i+1] 小于等于 0，说明从 i+1 开始往右的最大子段和是负的，那以 i 开头的最大子段和就应该只取 x[i] 本身，因为加上后面的负数只会让和变小；否则就可以继承 rmax[i+1]，即 rmax[i] = rmax[i+1] + x[i]。所以 (3) 填 if (rmax[i + 1] <= 0) rmax[i] = x[i]; else rmax[i] = rmax[i + 1] + x[i];。第四个空同样是 rmax 的单调性处理：和 lmax 一样，如果 rmax[i] 比 rmax[i+1] 小，说明以 i 开头的最大子段和不如以 i+1 开头的大，那就把 rmax[i] 更新为 rmax[i+1]，保证 rmax 数组单调不减。所以 (4) 填 if (rmax[i] < rmax[i + 1]) rmax[i] = rmax[i + 1];。最后一个空在枚举分隔点 i 时，sum 应该是 lmax[i-1] + rmax[i+1]，因为左子段最远到 i-1，右子段最近从 i+1 开始，中间 i 这个位置被跳过，满足‘间隔至少1个数’。所以 (5) 填 lmax[i-1] + rmax[i+1]。整个算法的时间复杂度是 O(n)，空间复杂度也是 O(n)，完全符合题目 n ≤ 1000 的限制。避坑提醒：千万别把 rmax 的初始化写错，或者忘记单调性处理，否则后面递推全是错的；也别把两个子段直接相邻地加起来，那样就违反了题意。从考频趋势看，一维数组相关题目在 NOIP 提高组初赛里非常常见，2023 年考了 27 题，2024 年更是飙到 48 题，2025 年达到 55 题，2026 年预测会考 59 题，说明这类基础但易错的动态规划题目是命题人的‘必考题’，未来大概率还会以类似形式出现，比如改成环形数组、或者增加第三个子段限制等。暂无足够依据预测具体变体，但可以确定的是，掌握这种‘预处理+单调性+枚举分隔点’的思路，对应对此类动态规划变种至关重要。