最大连续子段和

思路：

用两个变量 一个存放累计最大值 一个存放当前和 如果当前和小于0 则在这之前的数都pass掉 给当前和重新赋值
时间复杂度O(n)

code:

#include<iostream>
#include<cmath>
using namespace std;
const int N=2e5+5;
int n;
int a[N];
int maxs=-99999,thissum;//最大值与当前和
void getmax()
{
    maxs=a[1];//最大值默认为第一个元素的值
    thissum=a[1];//当前和也默认为第一个元素的值
    for(int i=2;i<=n;i++)
    {
        thissum+=a[i];//当前和 累加
        if(thissum<0) thissum=a[i];//如果当前和小于0 则放弃当前和
        maxs=max(maxs,thissum);//判断最大值是否改变
    }    
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    getmax();
    cout<<maxs<<endl;
    return 0; 
}