3066: Maximum sum

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<cstring>
#include<algorithm> 
using namespace std;
const int N = 5e4 + 10;
int a[N],f1[N],f2[N],t,n,m;
int main()
{
	cin >> t;
	while(t --){
		memset(a, 0, sizeof a);
		memset(f1, -0x3f, sizeof f1);
		memset(f2, -0x3f, sizeof f2);
		cin >> n;
		for(int i = 1 ;i <= n; i ++) cin >> a[i];
		for(int i = 1; i <= n; i ++)
			f1[i] = max(a[i], f1[i - 1] + a[i]);
		for(int i = n; i >= 1; i --)
			f2[i] = max(a[i], f2[i+1] + a[i]);
		
		for(int i = 1; i <= n; i ++)
			f1[i] = max(f1[i-1], f1[i]);
		for(int i = n; i >= 1; i --)
			f2[i] = max(f2[i+1], f2[i]);
		
		int ans = a[1];
		for(int i = 1;  i <= n; i ++){
			ans = max(ans, f1[i-1] + f2[i]);
		}
		cout << ans <<endl;		
	}			
	return 0;
}