洛谷:P1115 最大子段和
题目描述
给出一个长度为 n 的序列 a ,选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数,表示序列的长度 n 。
第二行有 n 个整数,第 i 个整数表示序列的第 i 个数字 ai.
输出格式
输出一行一个整数表示答案。
数据规模与约定
-
对于 40%40\%40% 的数据,保证 n≤2×103n leq 2 imes 10^3n≤2×103。 对于 100%100\%100% 的数据,保证 1≤n≤2×10^5 ,1x10^-4 <= a <= 1x10^4
写这道题的时候经历了很多曲折呢。。。。。。
和同学讨论了一下得出了最后的答案。
首先讲一下思路 :
一开始想到的是开三个数组的前缀和法,就是一个存储数据,一个存和,最后一个存每两个相减的结果,然后选出最小的,但是显然太复杂了;
然后想到用贪心的思想(我并没有学,但是了解一点点)
首先考虑第一种情况,全是负数,则只要选出最大的就行;
其它情况:就是用一个 x记录当前前缀和,一路累积过去,如果前缀和 x变成了负数,那么下一个数就不需要前面的数了(因为还不如只选它一个),这时把 x置为0,再继续累加
#include <iostream> using namespace std; int a[200001]; int main() { int n ; cin >> n; for(int i = 0;i < n;i++) { scanf("%d" ,&a[i]); } int x = 0,max = a[0]; for(int i = 0;i < n;i++) { x += a[i]; if(x >= max) max = x; if(x <= 0) x = 0; } cout << max; return 0; }