题解 | #最大子矩阵#

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;



class Solution {
    public int[][] matrix;
    public int[][] matrixSums;

    public Solution(int[][] matrix) {
        this.matrix = matrix;
        int n = matrix.length;
        matrixSums = new int[n][n];
        for (int i = 0; i < n; i++) {
            matrixSums[i] = Arrays.copyOf(matrix[i], matrix[i].length);
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrixSums[i][j] += matrixSums[i - 1][j];
            }
        }
    }

    static class ArrayMax {
        public int startIndex;
        public int endIndex;
        public int sum;

        public ArrayMax(int startIndex, int endIndex, int sum) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
            this.sum = sum;
        }

        public static ArrayMax getMaxArray(int[] nums) {
            int size = nums.length;
            int[] dp = new int[size];
            int[] pathStart = new int[size];
            Arrays.fill(pathStart, -1);
            dp[0] = nums[0];
            pathStart[0] = 0;
            int maxValue = dp[0];
            int maxIndex = 0;
            for (int i = 1; i < size; i++) {
                dp[i] = nums[i];
                if (dp[i - 1] > 0) {
                    dp[i] += dp[i - 1];
                    pathStart[i] = pathStart[i - 1];
                }

                if (maxValue < dp[i]) {
                    maxValue = dp[i];
                    maxIndex = i;
                }
            }
            return new ArrayMax(pathStart[maxIndex], maxIndex, dp[maxIndex]);
        }
    }
    public ArrayMax countValueOfMatrix(int start, int end) {
        int size = matrix.length;
        int[] nums = new int[size];
        for (int i = 0; i < size; i++) {
            nums[i] = matrixSums[end][i];
            if (start > 0)
                nums[i] -= matrixSums[start - 1][i];
        }

        return ArrayMax.getMaxArray(nums);
    }


}
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        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();
            }
        }

        int[][] dp = new int[n][n];
        int maxValue = Integer.MIN_VALUE;

        Solution solution = new Solution(matrix);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                dp[i][j] = solution.countValueOfMatrix(i, j).sum;
                maxValue = Math.max(maxValue, dp[i][j]);
            }
        }


        System.out.println(maxValue);



    }
}