最大子矩阵

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int m = Integer.parseInt(params[0]);
        int n = Integer.parseInt(params[1]);
        int[][] matrix = new int[n][n];
        for(int i = 0; i < m; i++){
            String[] row = br.readLine().split(" ");
            for(int j = 0; j < n; j++)
                matrix[i][j] = Integer.parseInt(row[j]);
        }
        int[][] calSum = new int[m][n];     // calSum[i][j]表示前i行第j列的元素之和
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++)
                calSum[i][j] = (i != 0? calSum[i - 1][j]: 0) + matrix[i][j];
        }
        int maxSize = Integer.MIN_VALUE;
        int[] colSum = new int[n];
        for(int startRow = -1; startRow < m; startRow ++){
            for(int endRow = startRow + 1; endRow < m; endRow ++){
                // 接下来与求数组的连续子数组最大和相同
                int sumBetweenStartrowAndEndrow = 0;
                int tempMaxSum = calSum[endRow][0] - (startRow == -1? 0: calSum[startRow][0]);
                int tempMinSum = tempMaxSum;
                for(int col = 0; col < n; col++)
                    sumBetweenStartrowAndEndrow += calSum[endRow][col] - (startRow == -1? 0: calSum[startRow][col]);
                for(int col = 1; col < n; col ++){
                    // startRow=-1需要求取第一行在第col列的和，由于第一行没有前缀和做差，所以需要特殊处理
                    colSum[col] = startRow == -1? calSum[endRow][col]: calSum[endRow][col] - calSum[startRow][col];
                    tempMaxSum = Math.max(colSum[col], colSum[col] + tempMaxSum);
                    tempMinSum = Math.min(colSum[col], colSum[col] + tempMinSum);
                    maxSize = Math.max(sumBetweenStartrowAndEndrow - tempMinSum, Math.max(maxSize, tempMaxSum));
                }
            }
        }
        System.out.println(maxSize);
    }
}