Largest Submatrix With Rearrangements

给一个0和1的二维矩阵, 求最大的全1子矩阵(不一定是square).

这个题首先观察例子, 发现肯定有排序, 然后再看一遍能看出来扫描可以通过查找连续1的个数来判断, 所以划分为一个个子问题, 即: 当扫完一行的时候, 如何计算当前的最大全是1的area. 我们需要先找到当前从上到下最多连续1的个数, 然后排序(greedy)后乘以当前的index后取最大.

class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[] longest = new int[m];
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(matrix[i][j] == 1){
                    longest[j]++;
                }
                else{
                    longest[j] = 0;
                }
            }
            int[] tmp = Arrays.copyOf(longest, m);
            Arrays.sort(tmp);
            for(int j = 0; j < m; j++) { 
                res = Math.max(res, tmp[m - j - 1] * (j + 1));
            }
        } 
        return res;
    }
}