Maximum sum
Time Limit:1000MSMemory Limit:65536K
Total Submissions:36100Accepted:11213
Description
Given a set of n integers: A={a1, a2,…, an}, we define a function d(A) as below:
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.
Output
Print exactly one line for each test case. The line should contain the integer d(A).
Sample Input
1101 -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.
1000ms，50000个数，所以每次处理的时间复杂度不能超过nlogn，否则会超时。所以要让最后扫描一次就能求出答案。
基本思路就是第一次遍历先定义2个数组，分别记录前i项和（含i）与后i项和（含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|1using 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_JUDGEfreopen("in.txt","r",stdin);#endif // ONLINE_JUDGEint tcase;scanf("%d",&tcase);while(tcase–){scanf("%d",&n);memset(prev,0,sizeof(prev));//前i项和（含i）memset(afte,0,sizeof(afte));//后i项和（含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;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，怕走崎岖路，莫想登高峰。
