Best Solution | C++
IntuitionTo solve this problem optimally, we need to make the best use of the column rearrangement to maximize the area of a submatrix consisting entirely of 1s
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
To solve this problem optimally, we need to make the best use of the column rearrangement to maximize the area of a submatrix consisting entirely of 1s

# Approach
<!-- Describe your approach to solving the problem. -->
We can treat each row of the matrix as a histogram of heights, where each element represents the number of consecutive 1s in the matrix up to that row. The idea is to calculate the maximum area of 1s you can get from the histogram by sorting the heights in non-decreasing order.

Step 1: Calculate Heights: Convert each row into a histogram of heights. For each column in the matrix, calculate the consecutive number of 1s from the current row upwards. If the element is 0, reset the height to 0.

Step 2: Sort Heights: After calculating the histogram of heights for each row, sort the heights in descending order for the maximum area calculation. Sorting ensures that we can maximize the rectangle area by using the largest heights first.

Step 3: Calculate Maximum Area: For each row, after sorting the heights, compute the area by multiplying the height by its column index (since the heights are sorted). Track the maximum area found.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Height computation: 

O(m×n), as we iterate through every element once.
Sorting each row: 

O(nlogn), as we sort each row individually.
Total: 
O(m×nlogn).

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(m×n)
# Code
```cpp []
#include <vector>
#include <algorithm>

class Solution {
public:
    int largestSubmatrix(std::vector<std::vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        
        // Convert matrix to height representation
        for (int i = 1; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] += matrix[i - 1][j];  // Accumulate heights
                }
            }
        }

        int maxArea = 0;
        
        // Process each row independently
        for (int i = 0; i < m; ++i) {
            // Sort the row in descending order
            std::vector<int> heights = matrix[i];
            std::sort(heights.rbegin(), heights.rend());  // Sort in decreasing order
            
            // Compute max area using sorted heights
            for (int j = 0; j < n; ++j) {
                maxArea = std::max(maxArea, heights[j] * (j + 1));
            }
        }

        return maxArea;
    }
};

```
['C++']