1727. Largest Submatrix With Rearrangements

• 이렇게 계산하면 특정 row의 위치에서 각 column 별로 걸쳐있는 연속된 숫자 1의 개수를 알 수 있다.

• 먼저 row에 있는 column 별 연속된 1의 개수를 내림차순으로 정렬한다.
• 첫번째 column 부터 시작하여 영역의 크기를 계산하고 그 중에 최대 값을 구한다.
• 현재 column의 index를 c 라고 할 때 영역의 크기는 아래의 그림과 같이 (c + 1) * matrix[r][c] 로 계산될 수 있다.

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int R = matrix.size();
        int C = matrix[0].size();
        int result = 0;
        for (int r = 1; r < R; ++r) {
            auto& prevRow = matrix[r - 1];
            auto& row = matrix[r];
            for (int c = 0; c < C; ++c) {
                if (row[c] != 0) row[c] += prevRow[c];
            }
        }
        for (int r = 0; r < R; ++r) {
            auto& row = matrix[r];
            sort(row.begin(), row.end(), greater<int>());
            for (int c = 0; c < C && row[c] > 0; ++c) {
                result = max(result, (c + 1) * row[c]);
            }
        }
        return result;
    }
};