洛谷: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;
}
