题解 | 最大子数组和

使用动态规划解决。

建立dp数组，初始化置零，dp[i]表示从首位到i的当前最大子数组的和。

因为数据范围-10000~10000，所以会有一种情况：前面的数的和加上当前数字，结果反而没有当前数字大，说明前面的数字的和是负数，拖了真正的大数(当前数字)的后腿。这种情况下就要丢掉前面的数，从当前数字算起。

数组从头部遍历到结尾，每次都是最优结果(保证目前的和最大)，所以最后才能得到最大子数组的和。

状态转移方程： dp[i] = max(v[i], dp[i-1] + v[i])

结果取dp数组中最大值即为答案。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,ans;
    cin>>n;
    vector<int> v(n+1),dp(n+1,0);
    for(int i=1;i<=n;++i) cin>>v[i];
    dp[1]=v[1];
    ans=dp[1];
    for(int i=2;i<=n;++i){
        dp[i]=max(v[i],v[i]+dp[i-1]);
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}