【洛谷】 P1115 最大子段和（贪心）
【洛谷】 P1115 最大子段和
问题描述 给出一段序列，选出其中连续且非空的一段使得这段和最大。
输入格式 第一行是一个正整数N(0<N<200000)，表示了序列的长度。 第二行包含N个绝对值不大于10000的整数Ai，描述了这段序列。
输出格式 一个整数，为最大的子段和。子段的最小长度为1。
输入样例 7 2 -4 3 -1 2 -4 3
输出样例 4
样例说明 2,−4,3,−1,2,−4,3中，最大的子段和为4，该子段为3,−1,2.
#include<iostream>
using namespace std;
int main()
{
int n,sum,max,now; // sum用于记录前缀和，max用于记录最大值，now用于记录当前输入的值
cin>>n>>sum; // 将输入序列的第一个作为sum
max = sum; // 将sum的值作为max的值
while(--n)
{
cin>>now;
sum = sum>0?sum:0; // 判断sum的正负以决定是否保留该序列
sum += now; // 无论怎样，都加上当前输入的值以对比max
max=max>sum?max:sum;
}
cout<<max<<endl;
return 0;
}
进阶题目：
