题解 | #最大子矩阵#动态规划之最大连续子序列和

1. 当i=j时，求最大子矩阵和就转换成了求第i行元素的最大连续子序列和。
2. 当i!=j时，将第i行到第j行的所有行的元素累加起来，得到只有一行的一维数组，这个一维数组的最大连续子序列和，便是最大子矩阵和。

import java.util.*;

public class Main {

    /**
     * 获得一维数组array的最大连续子序列和
     */
    private static int findGreatestSumOfSubArray(int[] array) {
        if (array.length == 0) {
            return 0;
        }
        int[] dp = new int[array.length];
        dp[0]=array[0];
        int max = array[0];
        for(int i=1;i<array.length;i++){
            dp[i]=Math.max(dp[i-1]+array[i],array[i]);
            max=Math.max(max,dp[i]);
        }
        return max;
    }

    /**
     * 获得矩阵matrix的最大子矩阵和
     */
    private static int findGreatestSumOfSubMatrix(int[][] matrix) {
        int[][] total = matrix;//辅助矩阵
        /**
         * 为了能够在原始矩阵里很快得到从 i 行到 j 行 的上下值之和，我们这里用到了一个辅助矩阵，它是原始矩阵从上到下加下来的
         */
        for (int i = 0; i < matrix.length; i++) {//初始化辅助矩阵
            for (int j = 0; j < matrix[0].length; j++) {
                if (i == 0) {
                    total[i][j] = matrix[i][j];
                } else {
                    total[i][j] += total[i - 1][j];
                }
            }
        }
        int ans = Integer.MIN_VALUE;
        //最大子矩阵为i到j行，i从0到length-1，j从i到length-1
        for (int i = 0; i < matrix.length; i++) {
            for (int j = i; j < matrix.length; j++) {
                //array 保存的是从 i 行 到第 j 行 所对应的矩阵上下值的和
                int[] array = new int[matrix[0].length];
                for (int k = 0; k < matrix[0].length; k++) {
                    //如果我们要求第 i 行到第 j 行之间上下值的和，我们可以通过total[j][k] - total[i-1][k] 得到,
                    //k 的范围从1 到 matrix[0].length - 1。
                    if (i == 0) {
                        //i为0，获得前j行的和
                        array[k] = total[j][k];
                    } else {
                        //i不为0，需要减去前i行的和，得到i行到j行的和
                        array[k] = total[j][k] - total[i - 1][k];
                    }
                }
                int max = findGreatestSumOfSubArray(array);
                ans = Math.max(max, ans);
            }

        }
        return ans;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[][] matrix = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = scanner.nextInt();
                }
            }
            System.out.println(findGreatestSumOfSubMatrix(matrix));
        }
    }
}