Source Code

Problem: 2479  User: yzhw 
Memory: 3380K  Time: 860MS 
Language: Java  Result: Accepted 

Source Code 
import java.io.*;
public class Main {

	/**
	 * @param args
	 */
		static int data[]=new int[50005];
		static long dp[]=new long[50005];
		static int num;
	public static void main(String[] args) throws IOException{
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		int testcase;
		in.nextToken();
		testcase=(int)in.nval;
		dp[0]=0;
		while(testcase--!=0)
		{
			in.nextToken();
			num=(int)in.nval;
			for(int i=1;i<=num;i++)
			{
				in.nextToken();
				data[i]=(int)in.nval;
			}
			long now=0,max=-Long.MAX_VALUE;
			for(int i=1;i<=num;i++)
			{
				if(now+data[i]>data[i]) now=now+data[i];
				else
				{
				  now=data[i];
				}
				if(now>max)
				{
					max=now;		
				}
				dp[i]=max;
				
			}
			now=0;
			max=-Long.MAX_VALUE;
			long total=-Long.MAX_VALUE;
			for(int i=num;i>1;i--)
			{
				if(now+data[i]>data[i]) now=now+data[i];
				else
				{
				  now=data[i];
				}
				if(now>max)
				{
					max=now;		
				}
				total=Math.max(total,dp[i-1]+max);
			}
	
			System.out.println(total);
			
		}

	}

}

• Re:我，AC了，贴代码 (22) xiaohaoshiyan 2010-05-29 14:56:45
• Re:我，AC了，贴代码 (15) eqyun 2010-05-29 15:19:34