P1115 最大子段和——题解

解题思路

扫描序列，cur 表示必须以当前位置结尾的最大子段和。它要么只取当前数，要么把当前数接在之前的最优结尾子段后面，所以 cur=max(a[i],cur+a[i])。用 ans 记录所有 cur 的最大值。

复杂度分析

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

易错点

子段必须非空，不能把初值设为 0，否则全负数时会出错。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;long long x,cur,ans;cin>>x;cur=ans=x;
    for(int i=2;i<=n;i++){cin>>x;cur=max(x,cur+x);ans=max(ans,cur);}
    cout<<ans<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n;cin>>n;long long x,cur,ans;cin>>x;cur=ans=x; for(int i=2;i<=n;i++){cin>>x;cur=max(x,cur+x);ans=max(ans,cur);} cout<<ans<<'\n';return 0; }