题解【最大子段和】

使用DP算法

---

本文设数组下标从1开始。
dp[1]=a[1] 因为一个数，选他就最大
接下来：
dp[i]：

• dp[i-1]+a[i]<0:dp[i]=0 a[1~i-1]的最大子段和加上a[i]小于零，那么就白手起家（bushi）
• 否则，dp[i]=dp[i-1]+a[i] 继续累加
• 统计dp表最大值，就是最大子段和

不用管为什么，模板背下来。
参考代码：

#include <iostream>
#include <algorithm> 
using namespace std;
int main() {
    int n;
    cin>>n;
    int a[200001],dp[200001],ans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[1]=a[1];
    for(int i=2;i<=n;i++){
       //自己写;
    }
    cout<<ans;
    return 0;
}