数据过水
查看原帖
数据过水
1124941
woden楼主2024/8/29 10:06

注释部分,正解是 n−1n-1,我写的是 n−2n-2,但是对了。

数据是不是有点水了?

#include<bits/stdc++.h>
#define int long long
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=1000000+99;
int n;
int a[N],f[N],g[N];
int doit(){
	for(int i=1;i<=n;i++){
		f[i]=max(f[i-1],0LL)+a[i];
	}
	for(int i=n;i>0;i--){
		g[i]=max(g[i+1],0LL)+a[i];
	}
	for(int i=2;i<=n;i++){
		f[i]=max(f[i],f[i-1]);
	}
	for(int i=n-2/*注意看这里*/;i>0;i--){
		g[i]=max(g[i],g[i+1]); 
	}
	int ans=LLONG_MIN;
	for(int i=2;i<n;i++){
		ans=max(ans,f[i-1]+g[i+1]);
	}
	return ans;
}
signed main(){
	fst;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cout<<doit();
	return 0;
}
2024/8/29 10:06
加载中...