最大子矩阵的和
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;}}