Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:弱问100+MS的大牛是如何做的~~我O(n)的做法也400+(附代码,请指教)

Posted by 351200 at 2011-10-26 20:03:37 on Problem 2479
In Reply To:弱问100+MS的大牛是如何做的~~我O(n)的做法也400+(附代码,请指教) Posted by:GreenBird at 2011-03-29 04:46:57
> #include<cstdio>
> int t,n,a[50000],b[50000],c[50000],i,temp,max;
> int main()
> {
> 	scanf("%d",&t);
> 	while(t--){
> 		scanf("%d",&n);
> 		for(i=0;i<n;i++)scanf("%d",&a[i]);
> 		b[0]=temp=a[0];
> 		for(i=1;i<n;i++){
> 			temp=a[i]+temp>a[i]?a[i]+temp:a[i];
> 			b[i]=temp>b[i-1]?temp:b[i-1];
> 		}
> 		c[n-1]=temp=a[n-1];
> 		for(i=n-2;i>=0;i--){
> 			temp=a[i]+temp>a[i]?a[i]+temp:a[i];
> 			c[i]=temp>c[i+1]?temp:c[i+1];
> 		}
> 		max=b[0]+c[1];
> 		for(i=2;i<n;i++)max=b[i-1]+c[i]>max?b[i-1]+c[i]:max;
> 		printf("%d\n",max);
> 	}
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator