最大子矩阵的和

package www.viking.com.algorithm;

public class MaxSubMatrixSum {

	/**
	 * @param args
	 * 
	 * 求子矩阵的最大和
	 *   | a11 …… a1i ……a1j ……a1n |
  	 *	 | a21 …… a2i ……a2j ……a2n |
     *   |  .   .  .  .  .  .  .  |
     *   |  .   .  .  .  .  .  .  |
     *   | ar1 …… ari ……arj ……arn |
     *   |  .   .  .  .  .  .  .  |
     *   |  .   .  .  .  .  .  .  |
     *   | ak1 …… aki ……akj ……akn |
     *   |  .   .  .  .  .  .  .  |
     *   | an1 …… ani ……anj ……ann |
     *   
     *   基本思路：
     *   
     *   假如我们知道从第i行到第j行为最大字段，那么我们把每列相加就和得到一个一维数组，
     *   就可以利用最大字段和的方法求解了。
     *   
     *   
     *   
     *   
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
        int[][]a={
        		{-1,3,-3,4,2},
        		{2,5,-1,8,7},
        		{-2,3,-3,2,2},
        		{7,4,-2,8,3},
        		{2,5,-7,9,1}
        };
      System.out.println(maxSubMatrixSum(a));
	}

	private static int n = 5;

	public static int maxSubMatrixSum(int[][] a) {
		int maxsum = a[0][0];
		int[] b = new int[n];
		for (int i = 0; i < n; i++) {
			for (int k = 0; k < n; k++) {
				b[k] = 0;
			}
			for (int j = i; j < n; j++) {
				//b[k]记录了从i到j-1的和，累加 i到j行列的和
				for (int k = 0; k < n; k++) {
					b[k] += a[j][k];
				}
				int sum = maxSubQuenceSum(b);
				if (sum > maxsum) {
					maxsum = sum;
				}
			}
		}
		return maxsum;
	}

	public static int maxSubQuenceSum(int[] b) {
		int maxsum = b[0];
		int sum = 0;
		for (int i = 0; i < b.length; i++) {
			if (sum > 0) {
				sum += b[i];
			} else {
				sum = b[i];
			}
			if (sum > maxsum) {
				maxsum = sum;
			}
		}
		return maxsum;
	}
}