题解 | #最大子矩阵#

import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int n = Integer.parseInt(br.readLine());
       int [][] arr = new int [n][n];
       int maxT = Integer.MIN_VALUE;
       //处理输入
       for(int i=0;i<n;i++){
        String [] s = br.readLine().split(" ");
        for(int j=0 ; j<n ; j++){
            arr[i][j] = Integer.parseInt(s[j]);
            //maxT =Math.max(maxT,arr[i][j]);
        }
       }
       //以某一个结点为
       int [][] dp = new int [n+1][n+1];
       for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(j==1){
                dp[i][j] = dp[i-1][j]+arr[i-1][j-1];
                continue;
            }
            else if(i==1){
                dp[i][j] = dp[i][j-1]+arr[i-1][j-1];
                continue;
            }
            else{
                dp[i][j]= dp[i-1][j];
                for(int m=1;m<=j;m++){
                    dp[i][j] +=arr[i-1][m-1];
                }
            }
        }
       }
       //(i,j)(k,m)分别表示对角顶点
       for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=i;k<=n;k++){
                for(int m=j;m<=n;m++){
                    int sq = dp[k][m] - dp[i-1][m] -dp[k][j-1] + dp[i-1][j-1] ;
                    maxT = Math.max(maxT,sq);
                    //System.out.println(maxT);
                }
            }
        }
       }
       System.out.println(maxT);
    }
}