最大子段和(洛谷 p1115)

Author Avatar
Axell 8月 08, 2018
  • 在其它设备中阅读本文章

思路

只需要从后往前扫描,sum累加(同时更新答案),当sum小于0时抛弃后面一段.
注意: 当数据全为负数时,ans的初始值应为数据中最小的一个.

代码

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

int n,a[200005],sum,ans;

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        scanf("%d",&a[i]),ans=min(ans,a[i]);
    for (int i=n;i>=1;i--){
        sum+=a[i];
        ans=max(ans,sum);
        if (sum<0){
            sum=0;
        }
    }
    printf("%d",ans);
    return 0;
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。

本文链接:https://axell.wind-flower.cn/archives/29/