题意可简化为:求解数组的最大子区间和,从左到右遍历数组,遍历到第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;
}