最大子矩阵的和

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;}}