NOIP 提高 2015 第一轮 第 27 题：完善程序（双子序列最大和）第 1 空

题目

（双子序列最大和）给定一个长度为 $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
                (3)    ;
    for (i = n - 2; i >= 0; i--)
        if (rmax[i] < rmax[i + 1])
                (4)    ;
    ans = x[0] + x[2];
    for (i = 1; i < n - 1; i++) {
        sum =     (5)    ;
        if (sum > ans)
            ans = sum;
    }
    cout << ans << endl;
    return 0;
}

第 1 空应填（ ）

答案

rmax[n-1]=x[n-1]

题解

考点定位

本题（完善程序「双子序列最大和」第①空）考「右侧初始化」,对应大纲 4.3.2 DP（难度【4】）。

程序思路：lmax[i]=「以 i 结尾/左侧」最大子段和、rmax[i]=「i 右侧」最大子段和，答案=max(lmax[i−1]+rmax[i+1])。

解题过程

①处在 lmax 递推后：rmax 末位初始化：

``cpp rmax[n-1] = x[n-1]; ``

答案：rmax[n−1]=x[n−1]。

易错提醒

① rmax 从右往左递推，先定种子；② lmax 也有同样的右移最大值传递（第二遍循环）。