Maximum sum
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 36100 | Accepted: 11213 |
Description
Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:
tex=d%28A%29%3D%5Cmax_%7B1%5Cleq+s_1%5Cleq+t_1%3Cs_2%5Cleq+t_2%5Cleq+n%7D%5Cleft%5C%7B%5Csum_%7Bi%3Ds_1%7D%5E%7Bt_1%7Da_i%2B%5Csum_%7Bj%3Ds_2%7D%5E%7Bt_2%7Da_j%5Cright%5C%7D&driver=1" alt="">
Your task is to calculate d(A).
Input
The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.
Output
Print exactly one line for each test case. The line should contain the integer d(A).
Sample Input
1 10
1 -1 2 2 3 -3 4 -4 5 -5
Sample Output
13
Hint
In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.
Huge input,scanf is recommended.
Huge input,scanf is recommended.
1000ms。50000个数，所以每次处理的时间复杂度不能超过nlogn，否则会超时。所以要让最后扫描一次就能求出答案。
基本思路就是第一次遍历先定义2个数组，分别记录前i项和（含i）与后n-i+1项和（含i）。
第二次遍历再定义2个数组。分别记录以i为终点（含i）的最大子段和与以i为起点（含i）的最大子段和。
第三次遍历再定义2个数组，分别记录第i项（含i）的之前的最大子段和与第i项（含i）的之后的最大子段和。最后遍历一遍数组求出i之前（含i）子段和与i之后（不含i）子段和的最大值就可以。
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma commment(linker,"/STACK: 102400000 102400000")
#define lson a,b,l,mid,cur<<1
#define rson a,b,mid+1,r,cur<<1|1
using namespace std;
const double eps=1e-6;
const int MAXN=50050; int num[MAXN],n,prev[MAXN],afte[MAXN],ans1[MAXN],ans2[MAXN],fans1[MAXN],fans2[MAXN],sum; int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
int tcase;
scanf("%d",&tcase);
while(tcase--)
{
scanf("%d",&n);
memset(prev,0,sizeof(prev));//前i项和（含i）
memset(afte,0,sizeof(afte));//后n-i+1项和（含i）
memset(ans1,0,sizeof(ans1));//以i为终点（含i）的最大子段和
memset(ans2,0,sizeof(ans2));//以i为起点（含i）的最大子段和
memset(fans1,0,sizeof(fans1));//第i项（含i）的之前的最大子段和
memset(fans2,0,sizeof(fans2));//第i项（含i）的之后的最大子段和
sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
prev[i]=prev[i-1]+num[i];
sum+=num[i];
}
if(n==2)
{
printf("%d\n",sum);
continue;
}
for(int i=n;i>=1;i--)
afte[i]=afte[i+1]+num[i];
int minn=0;
for(int i=0;i<n;i++)
{
minn=min(prev[i],minn);
ans1[i+1]=prev[i+1]-minn;
//printf("%d\n",ans1[i+1]);
}
minn=0;
for(int i=n+1;i>0;i--)
{
minn=min(afte[i],minn);
ans2[i-1]=afte[i-1]-minn;
//printf("%d\n",ans2[i-1]);
}
int maxx=-99999999;
for(int i=1;i<=n;i++)
{
maxx=max(maxx,ans1[i]);
fans1[i]=maxx;
}
maxx=-99999999;
for(int i=n;i>=1;i--)
{
maxx=max(maxx,ans2[i]);
fans2[i]=maxx;
}
int ans=-99999999;
for(int i=1;i<n;i++)
ans=max(ans,fans1[i]+fans2[i+1]);//题目规定区间不能有交集
printf("%d\n",ans);
}
return 0;
}