题库 信息学奥赛题库 题目列表 (双子序列最大和)给定一个长度为 n(3≤n≤1000) 的整...
组合题

(双子序列最大和)给定一个长度为 n(3≤n≤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 题 填空
第 2 题 填空
第 3 题 填空
第 4 题 填空
第 5 题 填空
题目信息
2015年 初赛
-
正确率
0
评论
50
点击