题解

new_user_2 2023-12-02 20:24:25

题意可简化为:求解数组的最大子区间和,从左到右遍历数组,遍历到第i点时,变量sum表示前i-1个数提供的攻击力,易知如果前i-1个数提供的攻击力为负,那么就应该舍弃前i-1个数而直接选取第i个数,遍历的过程中动态更新答案即可。注意有可能sum和答案有可能爆int,开long long 即可

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

int a[400050];
int n,m;


int main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    cin>>n;
    for(int x=1;x<=n;x++){
        cin>>a[x];
    }
    long long int sum=0;
    long long int ans=0;
    for(int x=1;x<=n;x++){
        if(sum<0){
            sum=0;
        }
        sum+=a[x];
        ans=max(sum,ans);
    }
    cout<<ans<<"\n";
    return 0;
}