题解 | #最大子矩阵#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型ArrayList<ArrayList<>>
     * @return int整型
     */
    public int getMaxMatrix (ArrayList<ArrayList<Integer>> matrix) {
        /*
           dp
           题解：
           首先，最大子矩阵和最小子矩阵是同一回事。
           我们先求出矩阵每一列的前缀和sum[i][j],i为列号，j为行号，然后枚举一个开始的行和一个结束的行，
           然后问题就转化成了最大子数组问题，最大子数组的前缀和就是sum[j][ed]-sum[j][st-1]
           最大子数组的解法就是遍历一遍数组，如果当前数字和为正数，就更新答案，如果为负数，则从下一个位置开始重新求和。
        */
        int n = matrix.size();
        int m = matrix.get(0).size();

        int ans = matrix.get(0).get(0);
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m ; j++) {
                ans = Math.min(ans, matrix.get(i).get(j));
            }
        }
        int mostmin = ans;
        for (int i = 0; i < n ; i++) {
            int[] help = new int[m];
            for (int row = i; row < n ; row++) {
                for (int col = 0; col < m ; col++) {
                    help[col] += matrix.get(row).get(col);
                }

                int cursum = f(help, mostmin);
                ans = Math.max(ans, cursum);
            }
        }

        return ans;
    }

    public int f(int[] arr, int max) {
        //max =Integer.MIN_VALUE;
        int tmp = 0;
        for (int i = 0; i < arr.length ; i++) {
            if (tmp > 0) tmp += arr[i];
            else
                tmp = arr[i];

            max = Math.max(max, tmp);
        }
        return max;
    }
}