A 22746.最大子段和

连续最大子段和可以看做依次读取数据，你可以对数据进行以下操作：
1.将此数据加入前面子段
2.此数据单独成一段
我们只需要取以上两种情况的较大值即可
接下来我们只需要定义一个maxn用来存储最大子段和

给出代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 

const int MAXN=200000;//顺带提示尽量别用2*1e5，因为是浮点数可能产生精度问题
ll a[MAXN];
ll dp; //中间量，跟动规有关，用的dp当变量名

int main(){
    ll n, maxn=-1e18;//使maxn的初始值小于测试数据的最小值
    cin >> n;
    for(ll i=1; i<=n; i++){
        cin >> a[i];
        if(i==1)
            dp=a[i];
        else
            dp=max(a[i], dp+a[i]);//加入子段或独立成段
        maxn=max(maxn, dp);//取最大子段和
    }
    cout << maxn;
    return 0;
}

时间复杂度：o(n),没有问题