本文主要是介绍SCAU 18708 最大子段和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
18708 最大子段和
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
一个整数序列，选出其中连续且非空的一段使得这段和最大。
注意当题目要求输入输出的数据量很大时，尽量使用scanf和printf。 c++提供的cin和cout速度比较慢，有可能在读取数据和输出数据时导致超时。
输入格式
第一行是一个正整数N，表示了序列的长度（0=<N<=200000）。
第二行包含N个绝对值不大于10000的整数ai。
输出格式
一个整数，为最大的子段和。子段的最小长度为1。数据确保结果在类型int范围内。
输入样例
7
2 -4 3 -1 2 -4 3
输出样例
4
提示
【样例说明】
2,-4,3,-1,2,-4,3中，最大的子段和为4，该子段为第三元素至第五元素，即3,-1,2。
前缀和
前缀和数组sum[i]
i位数字内最大差值必为sum[i]-minnum
其中minnum 表示i前的连续子段和的最小值
时间复杂度n
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200010;
int n,a[N],sum[N],minnum=10010,ans;int main()
{ios::sync_with_stdio(0), cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];sum[i] += sum[i - 1] + a[i];ans = max(ans, sum[i] - minnum);minnum = min(minnum, sum[i]);}cout << ans;return 0;
}
动态规划
include<iostream>
#include<algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
long long a[200001],sum,ans;
int main()
{long long n, i;scanf("%lld",&n); for (i=1; i <= n; i++){scanf("%lld", &a[i]); } for (i = 0; i < n; i++){sum += a[i];if (ans < sum)ans = sum;if (sum < 0)sum = 0;}printf("%lld",ans);return 0;
}
这篇关于SCAU 18708 最大子段和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
