题解 | 最大子矩阵-O(n^4)

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] matrix = new int[n][n];
        for (int i = 0; i < matrix[0].length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                matrix[i][j] = in.nextInt();
            }
        }
        System.out.println(finMaxSubMatrix(matrix));
    }
    public static int finMaxSubMatrix(int[][] matrix) {
        int res = Integer.MIN_VALUE;
        int[][] dp = new int[matrix.length][matrix[0].length];
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < matrix[0].length; i++) dp[0][i] = dp[0][i - 1] + matrix[0][i];
        for (int j = 1; j < matrix.length; j++) dp[j][0] = dp[j - 1][0] + matrix[j][0];

        for (int i = 1; i < matrix[0].length; i++) {
            for (int j = 1; j < matrix.length; j++) {
                dp[i][j] = matrix[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }

        //遍历，对于每一个右下角，枚举其左上角
        int curMatrix = 0;
        for (int i = 0; i < matrix[0].length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                //右下角i，j
                for (int u = 0; u <= i; u++) {
                    for (int v = 0; v <= j; v++) {
                        //左上角u，v
                        int a = dp[i][j];
                        int b = safeGet(dp, u - 1, v - 1);
                        int c = safeGet(dp, u - 1, j);
                        int d = safeGet(dp, i, v - 1);
                        curMatrix = a + b - c - d;
                        res = Math.max(curMatrix, res);
                    }
                }
            }
        }

        return res;
    }
    private static int safeGet(int[][]matrix, int i, int j) {
        int res = 0;
        try {
            res = matrix[i][j];
        } catch (Exception e) {}
        return res;
    }

}