tothemax.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.Scanner;


/**
 * ID:1050
 * 动态规划
 * @author yhm
 *
 */
public class TotheMax {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int size = cin.nextInt();
			short[][] matrix = new short[size][size];
			for(int i=0;i<size;i++){
				for(int j=0;j<size;j++){
					matrix[i][j] = cin.nextShort();
				}
			}
			int r = solve(matrix, size);
			System.out.println(r);
		}

	}
	
	static int solve(short[][] matrix,int size){
		short max = -128;
		for(int startRow=0;startRow<size;startRow++){
			for(int endRow=0;endRow<size;endRow++){
				short[] array = new short[size];
				for(int col=0;col<size;col++){
					for(int row=startRow;row<=endRow;row++){
						array[col]+=matrix[row][col];
					}
				}
				short temp = findMaxSeq(array);
				max = max>temp?max:temp;
			}
		}
		return max;
	}
	
	static short findMaxSeq(short[] seq){
		short max = -128;
		int size = seq.length;
		short[] result = new short[size];
		result[0] = seq[0];
		max = max>result[0]?max:result[0];
		for(int i=1;i<size;i++){
			if(result[i-1]>0){
				result[i] = (short)(result[i-1]+ seq[i]);
			}
			else{
				result[i] = seq[i];
			}
			max = max>result[i]?max:result[i];
		}
		return max;
	}
}