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

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

"NOIP真题" 试卷中 NOIP第二十一届全国青少年信息学奥林匹克联赛初赛试题[2015提高组] 中有题目如下：

(双子序列最大和)给定一个长度为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;
}

共 13 分　

所属试卷：NOIP第二十一届全国青少年信息学奥林匹克联赛初赛试题[2015提高组]

其它题目

在下列链表中，能够从任意一个结点出发直接访问到所有结点

抽象类是（）。

一棵二叉搜索树如题 7 图所示，k1、k2、k3 分别

有以下程序段执行上述语句后，m和n的值分别是（）。

以下函数findmax拟实现在数组中查找最大值并作为函

有以下程序段以下选项中表达式的值为11的是。

若函数中有定义语句：则。

代码 print(1,2,3,sep=':')的执行结

假设已成功导入Python标准库string，那么表达

编写程序，其功能为打印如下图所示图形。**** ***

#编写程序，其功能为打印如下图所示图形。*******

若运行一下程序时输入:-2<回车>，则程序的输出结果是

下列那个不是局域网的特点（）

改变命令提示符的环境变量是

将前一个命令的标准输出作为后一个命令的标准输入，称之为

将/home/stud1/wang目录做归档压缩，压缩

安装Linux系统对硬盘分区时，必须有两种分区类 __

创建表时使用 ____ 或key参数可定义索引。

数据库应用系统设计的需求分析阶段生成的文档主要有数据字

数据管理技术发展过程中,（）不是文件系统阶段的特点。

链式存储结构失去了顺序存储结构的按序号随机存取的特点，

(第k小路径)给定一张.个点.条边的有向无环图，顶点编

按软件的功能进行划分，软件可以划分为、、

考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据

设x=4<4-!0，x的值为_____。

每个学校有一名校长，且不同学校的校长可以是同一人，则实

（质因数分解）给出正整数 n，请输出将 n质因数分解的

在 NOI 期间，主办单位为了欢迎来自各国的选手，举行

输入：114 5 6 6 4 3 3 2 3 2 1输

（字符串替换）给定一个字符串 S（S 仅包含大小写字

更多选择题

更多填空题

题量:	0 道
总分:	分

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷