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

救命啊 我要疯了 牛人帮我看下,是不是我漏了什么啊?

Posted by poin at 2009-05-14 14:30:45 on Problem 2593
#include<stdio.h>
#include<stdlib.h>

int b[100001][2];
int a[100001];

void dyn(int n)
{
	int i;
	b[0][0]=a[0];
	b[0][1]=a[n-1];
	
	for(i=1;i<n;++i){
		if(b[i-1][0]>0) b[i][0]=b[i-1][0]+a[i];
		else b[i][0]=a[i];
	}
	for(i=1;i<n;++i){
		if(b[i-1][1]>0) b[i][1]=b[i-1][1]+a[n-1-i];
		else b[i][1]=a[n-1-i];
	}
	for(i=1;i<n;++i){
		if(b[i-1][1]>b[i][1]) b[i][1]=b[i-1][1];
	}

}


int main()
{
    
	int n,i,t,max,first=-1000;
	int secont,count=0;
	secont=first;
	scanf("%d",&n);
	while(n){
		
        for(i=0;i<n;++i){
			scanf("%d",&a[i]);
		}
		for(i=0;i<n;++i) b[i][0]=b[i][1]=-1000;
		if(n==1) printf("%d\n",a[0]);
		else{
	    	dyn(n);
	        max=-100000001;
			first=secont=-1000;
	    	for(i=0;i<n;++i){
                if(first<a[i]) { first=a[i];t=i;}
		    	if(a[i]>=0) count++;
			}
	
	    	for(i=0;i<n;++i){
			
			  if(i!=t&&secont<a[i]) secont=a[i];
			}
		  
	    	if(count==0||count==1) {printf("%d\n",first+secont);}
		
		    else{
	         	for(i=0;i<n;++i){
		    	if(b[i][0]+b[n-2-i][1]>max) max=b[i][0]+b[n-2-i][1];
				}
			    printf("%d\n",max);
			}
		}
	
       scanf("%d",&n);
	}
	return 0;
}


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