---
# System prepended metadata

title: 1727. Largest Submatrix With Rearrangements
tags: [Leetcode, Medium, Greedy]

---

# 1727. Largest Submatrix With Rearrangements
###### tags: `Leetcode` `Medium` `Greedy`
Link: https://leetcode.com/problems/largest-submatrix-with-rearrangements/
## 思路 $O(MN)$ $O(1)$
首先计算出每个column里面连续的1的个数
然后把每一行sort起来
从后面往前算面积
## Code
```java=
class Solution {
    public int largestSubmatrix(int[][] matrix) {
        // compute number of consecutive ones in one column
        for(int i=1; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                if(matrix[i][j]==1){
                    matrix[i][j] = matrix[i-1][j]+1;
                }
            }
        }
        
        int ans = 0;
        for(int i=0; i<matrix.length; i++){
            Arrays.sort(matrix[i]);
            for(int j=matrix[0].length-1; j>=0; j--){
                ans = Math.max(ans, (matrix[0].length-j)*matrix[i][j]);
            }
        }
        return ans;
    }
}
```