题解 | #最大子矩阵#

动态规划：

利用题题目DP5（连续自数字最大和）的思路，首先将矩阵分为第一列，第二列... 用字母表示：m0,m1,m2...m(n-1)，得到n个数组，然后：

1. 先求第一个数组的最大子数组值a1。
2. 求第一个数组+第二个数组得到的数组的最大子数组值a2。
3. m0+m1+m2的最大子数组值a3
4. m0+...+m(n-1)的最大子数组值an
5. 在这些个a1...an中找到最大值为有包含第一列子数组的情况下的最大子矩阵。

第二次从第二列子数组作为起始数组，再循环上述步骤。

得到的是最大值包含有第二列子数组的情况下的最大子矩阵。 以此类推到最后一个子数组。

public class Main{
    
//    public static int maxMatrix(int[][]matrix){
//        int res=Integer.MIN_VALUE;
//        int n=matrix.length;
//        int m=matrix[0].length;
//        for(int i=0;i<n;i++){
//            for(int j=0;j<m;j++){
//                int [][]temp=new int[n-i][m-j];
//                copyMatrix(matrix,temp);
//                int curMax=maxValue(temp);
//                res=Math.max(curMax,res);
//            }
//        }
//        return res;
//    }
   
//    public static void copyMatrix(int[][] m1,int [][]m2){
//        int x=m1.length-1;
//        int y=m1[0].length-1;
//        for(int i=m2.length-1;i>-1;i--){
//            for(int j=m2[0].length-1;j>-1;j--){
//                m2[i][j]=m1[x][y--];
//            }
//            x--;
//            y=m1[0].length-1;
//        }
//    }
//    public static int maxValue(int[][]matrix){
//        int max=Integer.MIN_VALUE;
//        int n=matrix.length;
//        int m=matrix[0].length;
//        int[][] v=new int [n+1][m+1];
//         for(int i=1;i<=n;i++){
//             for(int j=1;j<=m;j++){
//                 v[i][j]=matrix[i-1][j-1]+v[i-1][j]+v[i][j-1]-v[i-1][j-1];
//                 max=max>v[i][j]?max:v[i][j];
//             }
//         }
//        return max;
//    } 
    //方法二：DP
    public static int maxMatrix(int [][]matrix){
        int max=Integer.MIN_VALUE;
        for(int i=0;i<matrix.length;i++){
            max=Math.max(max,process(matrix,i));
        }
        return max;
    }
    //得到从第i列到最后一列的所有子矩阵最大值
    public static int process(int[][] matrix,int firstCol){
        int row=matrix.length;
        int col=matrix[0].length;
        int[]dp=new int[row];
        int max=Integer.MIN_VALUE;
        for(int i=firstCol;i<col;i++){
            //dp更新
             for(int j=0;j<row;j++){
                dp[j]=dp[j]+matrix[j][i];
            }
            max=Math.max(max,findSubArrayMax(dp));
        }
        return max;
    }
    //求以dp维数组的子数组最大值
    public static int findSubArrayMax(int[] arr){
        int n=arr.length;
        int[] dp=new int[n];
        int max=arr[0];
        dp[0]=arr[0];
        for(int i=1;i<n;i++){
           dp[i]=dp[i-1]<0?arr[i]:dp[i-1]+arr[i];
            max=Math.max(dp[i],max);
        }
        return max;
    }

    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[][]matrix=new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                matrix[i][j]=sc.nextInt();
            }
        }
        System.out.print(maxMatrix(matrix));
    }
}