题解 | 最大子段和

选子数组的操作可用动态规划解决，动态规划的作用就是利用已处理的数据来推到之后的数据，对于子数组往里面加连续的数字我们可以想到定义dp[i]为遍历到i时的最大字段和，这样i+1可以判断是否要与之连接，简单的，如果dp[i-1]是正数那么我们就把他加进来，如果是负数就从当前作为左端点开始重新录入子数组，同时在这个过程中用一个maxn来记录最大的那个数值

#include <iostream>
using namespace std;
#define ll long long
const int N=2e5+5;
int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    ll n,num;
    cin>>n;
    ll dp[N];ll maxn=-1145141919810;dp[0]=0;
    for(int i=1;i<=n;i++){
        cin>>num;
        if(dp[i-1]>0)dp[i]=dp[i-1]+num;
        else dp[i]=num;
        maxn=max(maxn,dp[i]);
    }
    cout<<maxn;
}
// 64 位输出请用 printf("%lld")