题解 | 连续子数组最大和(ACM版本)

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

int main() {
    int n;
    cin>>n;

    vector<int> nums(n+1);

    for(int i=1;i<=n;i++)
    {
        cin>>nums[i];
    }

    vector<int> dp(n+1,0);
    dp[1]=nums[1];
    int maxsum=dp[1];

    for(int i=2;i<=n;i++)
    {
        dp[i]=max(dp[i-1]+nums[i],nums[i]);  //选择加上nums[i]或者重新以nums[i]开头
        maxsum=max(maxsum,dp[i]);
    }
    cout<<maxsum<<endl;
    return 0;
}

// 64 位输出请用 printf("%lld")