dp专题 最大子段和

``给你一个序列，求它的最大子段和

dp[i]表示以第i个数字为结尾的最大子段和

dp[i]=max(dp[i-1]+a[i], a[i]);
边界条件：dp[0]=0;

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

int a[200005];
int dp[200005]={0};
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i-1]+a[i], a[i]);
    }
    cout<<*max_element(dp+1, dp+n+1)<<endl;

    return 0;
}