学步园

考察点：动态规划

　　思路：虽然题目给出了3000ms的时间，但考虑到数据量可以达到100000，如果用O(N^2)的算法的话，还是极有可能会超时的，于是决定采用这种O(N)时间效率的动规。在输入的同时，进行一次DP，计算出从左到右的最大值，并把它保存在数组dp的对应的下标元素中，这样之后，对于下标为i 的元素，它其中保存的便是前面所有元素可能的最大连续和。再从右到左进行一次DP，计算从右到左的最大连续和。假设此时已经算到下标为i的元素，那么将 sum+dp[i-1]与ans进行比较，将ans取较大者。

import java.util.Scanner;
public class Main {
	
	public static void main(String[] args) {
	  Scanner scanner=new Scanner(System.in);
	  while(scanner.hasNext())
	  {
		 int number=scanner.nextInt();
		 if(number==0)break;
		 int result[]=new int[number];
		 int dp[]=new int[number];
		 int max=-999,sum1=0;
		 for(int i=0;i<number;i++)
		 {
			 result[i]=scanner.nextInt();
			 sum1+=result[i];
			 if(sum1>max)
				 max=sum1;
			 dp[i]=max;
			 if(sum1<0)
				 sum1=0;
		 }
		 
		 int sum2=0,answer=-999;
		 for(int i=number-1;i>0;i--)
		 {
			 sum2+=result[i];
			 if(dp[i-1]+sum2>answer)
				 answer=dp[i-1]+sum2;
			 if(sum2<0)
				 sum2=0;
		 }
		 System.out.println(answer);
	  }
	}
}