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;
}
}