编程之美-子数组的最大和（二维）

package beautyOfCoding;

import java.util.Arrays;
import java.util.Random;

public class MaxSubArraySum2 {

	/**
	 * 编程之美 子数组之和的最大值（二维）
	 */
	private static final int ROW = 5;
	private static final int COL = 6;
	private static final int MAX = 127;
	private boolean invalidInput = false;
	private static int[] source;	//[-127,127]共127*2+1个数
	static {
		int n = MAX * 2 + 1;
		source = new int[n];
		for (int i = 0; i < n; i++) {
			source[i] = i - MAX;
		}
	}

	public static void main(String[] args) {
		//生成指定行数和列数的数组。数组元素是[-127,127]范围内的随机数
		int[][] B = new int[ROW][COL];
		int n = MAX * 2 + 1;
		Random random = new Random();
		for (int i = 0; i < ROW; i++) {
			for (int j = 0; j < COL; j++) {
				int pos = random.nextInt(n);
				int num = source[pos];
				B[i][j] =  num;
			}
			System.out.println(Arrays.toString(B[i]));
		}
		
		/*int[][] B = {
				{0, -2, -7, 0},
				{9, 2, -6, 2},
				{-4, 1, -4, 1},
				{-1, 8, 0, -2}
		};*/
		
		//方法A-全枚举
		MaxSubArraySum2 test = new MaxSubArraySum2();
		int max = test.maxSubArraySumA(B);
		if (test.invalidInput) {
			System.out.println("invalid input");
		} else {
			System.out.println(max);
		}
		//方法B-部分和
		MaxSubArraySum2 test2 = new MaxSubArraySum2();
		int max2 = test2.maxSubArraySumB(B);
		if (test2.invalidInput) {
			System.out.println("invalid input");
		} else {
			System.out.println(max2);
		}
		//方法C-转化为一维
		MaxSubArraySum2 test3 = new MaxSubArraySum2();
		int max3 = test3.maxSubArraySumB(B);
		if (test3.invalidInput) {
			System.out.println("invalid input");
		} else {
			System.out.println(max3);
		}
	}

	/**
	 * 转化为一维。
	 */
	public int maxSubArraySumC(int[][] B) {
		int max = Integer.MIN_VALUE;
		if (B == null) {
			invalidInput = true;
		} else {
			int row = B.length;
			for (int a = 0; a < row; a++) {
				for (int c = a; c < row; c++) {
					int[] BC = this.getBC(B, a, c);
					int oneDimension = this.maxInOneDimensionalArray(BC);
					if (max < oneDimension) {
						max = oneDimension;
					}
				}
			}
		}
		return max;
	}
	
	/**
	 * maxSubArraySumC的辅助方法。得到第a行到第c行所代表的一维数组
	 */
	public int[] getBC(int[][] B,int a,int c){
		int col=B[0].length;
		int[] BC = new int[col];
		for(int i=0;i<col;i++){
			for(int j=a;j<=c;j++){
				BC[i] += B[j][i];
			}
		}
		return BC;
	}
	
	//子数组之和的最大值-一维
	public int maxInOneDimensionalArray(int[] a){
		//略去参数检查  
        int Start=0;  
        int All=0;  
        for(int i=0,len=a.length;i<len;i++){  
            All=this.maxNum(a[i],Start+a[i],All);  
            Start=this.maxNum(a[i],a[i]+Start);     //if start<0, start=a[i]  
        } 
        return All;
	}
	
	/**
	 * 用部分和的形式。其中辅助数组PS额外多一行多一列（默认初始化为0），方便计算“部分和”的“部分和”，需仔细体会
	 * PS[i][j] 表示元素(1,1)(对应原始数组B的B[0][0])和当前元素(i,j)为顶点对的子矩阵的部分和，部分和的计算如下：
	 * PS[i][j] = A[i][j]+PS[i-1][j]+PS[i][j-1]-PS[i-1][j-1]
	 */
	public int maxSubArraySumB(int[][] B) {
		int max = Integer.MIN_VALUE;
		if (B == null) {
			invalidInput = true;
		} else {
			int row = B.length;
			int col = B[0].length;
			int[][] PS = new int[row+1][col+1];
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					PS[i+1][j+1] = PS[i][j+1] + PS[i+1][j ] - PS[i][j] + B[i][j];
				}
			}
			max = this.maxPSij(PS);
		}
		return max;
	}
	
	/**
	 * maxSubArraySumB的辅助方法
	 * 求“部分和”的“部分和”：求得(imin, imax, jmin, jmax)代表的矩形区域的和，即题目所求
	 */
	public int maxPSij(int[][] PS) {
		int max = Integer.MIN_VALUE;
		int row = PS.length;
		int col = PS[0].length;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				for (int m = i; m < row; m++) {
					for (int n = j; n < col; n++) {
						max = this.maxNum(max, PS[i][j], PS[m][n], 
								(PS[m][n] - PS[m][j] - PS[i][n] + PS[i][j]));
					}
				}
			}
		}
		return max;

	}

	/**
	 * 穷举法，求部分和也是用枚举，有六个for循环，复杂度相当高，不过可用于检验其他方法是否正确
	 */
	public int maxSubArraySumA(int[][] B) {
		int max = Integer.MIN_VALUE;
		if (B == null) {
			invalidInput = true;
		} else {
			int row = B.length;
			int col = B[0].length;
			for (int imin = 0; imin < row; imin++) {
				for (int imax = imin; imax < row; imax++) {
					for (int jmin = 0; jmin < col; jmin++) {
						for (int jmax = jmin; jmax < col; jmax++) {
							int tmpSum = sum(B, imin, imax, jmin, jmax);
							if (tmpSum > max) {
								max = tmpSum;
							}
						}
					}
				}
			}
		}
		return max;
	}
	
	/**
	 * maxSubArraySumA的辅助方法
	 * 枚举求得(imin, imax, jmin, jmax)代表的矩形区域的和
	 */
	public int sum(int[][] B, int imin, int imax, int jmin, int jmax) {
		int result = 0;
		for (int i = imin; i <= imax; i++) {
			for (int j = jmin; j <= jmax; j++) {
				result += B[i][j];
			}
		}
		return result;
	}

	/**
	 * 返回最大的数
	 */
	public int maxNum(int x, int... yy) {
		for (int y : yy) {
			if (x < y) {
				x = y;
			}
		}
		return x;
	}
	
}