题目描述 给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中1≤i≤j≤K, 10000>=Ni >=-10000。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。 本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下： 数据1：与样例等价，测试基本正确性； 数据2：100个随机整数； 数据3：1000个随机整数； 数据4：10000个随机整数； 数据5：100000个随机整数； 数据6： 整数全为负数； 输入 输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。 输出 在一行中输出最大子列和。如果序列中所有整数都为负数，则输出0。输出代码

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100010;

int main() {
int k;
int arr[MAXN]; // 存放序列
cin >> k;
for (int i = 0; i < k; i++) {
cin >> arr[i];
}
int sum = 0, ans = -1;
for (int i = 0; i < k; i++) {
sum += arr[i];
ans = max(ans, sum); // 更新最大子列和
if (sum < 0) {
sum = 0; // 如果当前子列和为负数，则舍去，从下一个数重新开始累加
}
}
cout << ans << endl;
return 0;
}

相关问题

新生赛获奖证书请到逸夫楼117签名领取。未领取图书奖品的同学3月17日上午联系向老师领取（18607323285） 本部获奖名单 潇湘获奖名单 问题 A: 最大子列和问题 时间限制: 50 Sec 内存限制: 64 MB 提交: 1090 解决: 542 [状态] [提交] [命题人:1805010120] 题目描述 给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中1≤i≤j≤K, 10000>=Ni >=-10000。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。 本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下： 数据1：与样例等价，测试基本正确性； 数据2：100个随机整数； 数据3：1000个随机整数； 数据4：10000个随机整数； 数据5：100000个随机整数； 数据6： 整数全为负数； 输入 输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。 输出 在一行中输出最大子列和。如果序列中所有整数都为负数，则输出0。

题解

这题其实是一个经典问题，叫做最大子段和问题，可以用分治、动态规划、贪心等多种方法解决。这里介绍一下比较常用的动态规划方法。

设 $sum[i]$ 表示以第 $i$ 个数结尾的最大子段和，那么有：

$$sum[i]=\begin{cases}num[i] & i=1 \\ max\{sum[i-1]+num[i],num[i]\} & i>1\end{cases}$$

其中 $num[i]$ 表示第 $i$ 个数。

最终答案是所有 $sum[i]$ 中的最大值。

代码