题解 | 最大子段和

要求解最大子数组的和，先要弄清楚它的状态方程，使用dp[i]来表示以i结束的子数组中和最大的值，分2种情况：

1.dp[i] = a[i],

这种情况发生在dp[i-1]小于0时

2.dp[i] = dp[i+1] +a[i];

当以i-1结尾的最大子数组和不为0时，发生.

使用一个max来记录dp数组中的最大值.

最后输出max即可.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    vector<long long>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<long long>dp(n);//dp中dp[i]表示以i借位的连续数组的最大的和.
    long long m=a[0];
    //int mpos=0;
    dp[0] = a[0];
    for(int i=1;i<n;i++){
        dp[i] = max(a[i],dp[i-1]+a[i]);
        if(m<dp[i]){
            //mpos = i;
        }
        m = max(m,dp[i]);
    }
    //cout<<mpos<<endl;
    cout<<m;
}