PKU ACM 2479(Maximum sum)跟2593(Max Sequence)的动态规划解法(JAVA实现)

PKU ACM 2479(Maximum sum)和2593(Max Sequence)的动态规划解法(JAVA实现)

由于两道题实际为同一道题，故仅贴出2593的解法：

(值得注意的是，由于2479的时间要求较为严格，故最好使用StreamTokenizer处理输入，我试过换成Scanner，但始终超时！)

package problem2593;

import java.io.*;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		
		while(true)
		{
			in.nextToken();
			int num = (int)in.nval;
			if(num == 0)
				break;
			int [] val = new int[num];
			for(int i = 0; i < num; i++)
			{
				in.nextToken();
				val[i] = (int)in.nval;
			}
				
			int [] max = new int[num - 1];
			int current, maxVal, maxSum;
			max[0] = maxVal = val[0];
			maxSum = current = Math.max(val[0], 0);
			
			for(int j = 1; j < num - 1; j++)
			{
				current = Math.max(current + val[j], 0);
				if(current > maxSum)
					maxSum = current;
				
				maxVal = Math.max(maxVal, val[j]);
				if(maxVal < 0)
					max[j] = maxVal;
				else
					max[j] = maxSum;
			}
			
			maxVal = val[num - 1];
			maxSum = current = Math.max(val[num - 1], 0);
			int result = Integer.MIN_VALUE;
			result = val[num - 1] + max[num - 2];
			
			for(int j = num - 2; j >= 1; j--)
			{
				current = Math.max(current + val[j], 0);
				if(current > maxSum)
					maxSum = current;
				
				maxVal = Math.max(maxVal, val[j]);
				int temp;
				if(maxVal < 0)
					temp = maxVal + max[j - 1];
				else
					temp = maxSum + max[j - 1];
				
				if(temp > result)
					result = temp;
			}
			System.out.println(result);			
		}
	}
}