Leetcode 1727. Largest Submatrix With Rearrangements

[Woodyiiiiiii]

这道题跟85. Maximal Rectangle有些类似。

根据题意，我们可以随意排序，组成我们想要的最大面积。所以，我们要根据贪心的思想，尽可能地要把多的同在一行的1集中在一起，这就想到排序；接着，在循环中用累加计算当前列的最大高度，再进行贪心排序。

class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            List<Integer> dp = new ArrayList<>();
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 1 && i > 0) {
                    matrix[i][j] += matrix[i - 1][j];
                }
                dp.add(matrix[i][j]);
            }
            dp.sort(Collections.reverseOrder());
            for (int j = 0; j < n; ++j) {
                ans = Math.max(ans, dp.get(j) * (j + 1));
            }
        }
        return ans;
    }
}

---

• 1727. Largest Submatrix With Rearrangements