(双子序列最大和)给定一个长度为n(3≤n≤1000)

(双子序列最大和)给定一个长度为n(3≤n≤1000) 的整数序列,要求从中选出两个连续子序列,使得这两个连续子序列的序列和之和最大,最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求:每个连续子序列长度至少为 1,且两个连续子序列之间至少间隔 1 个数。

#include <iostrea m>
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];
    ①;
    for (i = n - 2; i >= 0; i --)
        if (rmax[i + 1] <= 0)
            ②;
        else
            ③;
    for (i = n - 2; i >= 0; i --)
        if (rmax[i] < rmax[i + 1])
            ④;
    ans = x[ 0] + x [2];
    for (i = 1; i < n - 1; i++) {
        sum = ⑤;
        if (sum > ans)
            ans = sum;
    }
    cout << ans << endl;
    return 0;
}


答案
第1空:rmax[n - 1] = x[n - 1]
第2空:rmax[i] = x[i]
第3空:rmax[i] = rmax[i + 1] + x[i]
第4空:rmax[i] = rmax[i + 1]
第5空:lmax[i + 1] + rmax[i + 1]

题目信息

题号:6638
题型:填空题
难度:普通