Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 1727. Largest Submatrix With Rearrangements

---

參考資訊：
https://algo.monster/liteproblems/1727
https://ithelp.ithome.com.tw/articles/10332259?sc=rss.iron
https://kevinchung0921.medium.com/leetcode-%E8%A7%A3%E9%A1%8C%E7%B4%80%E9%8C%84-1727-largest-submatrix-with-rearrangements-a80b251f08f3

題目：


方法：


Step 1. 原始矩陣


Step 2. 每一列從下往上計算連續1的次數


Step 3. 每一行做排序，最大的放在最左邊


Step 4. 位置(從1開始)乘上數字取最大值

3 * 1 = 3
0 * 2 = 0
0 * 3 = 0
 
2 * 1 = 2
2 * 2 = 4
1 * 3 = 3
 
1 * 1 = 1
1 * 2 = 2
0 * 1 = 0 

解答：

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int r = 0;
        int row_size = matrix.size();
        int col_size = matrix[0].size();
      
        for (int i = 1; i < row_size; ++i) {
            for (int j = 0; j < col_size; ++j) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] = matrix[i - 1][j] + 1;
                }
            }
        }

        for (auto& c : matrix) {
            sort(c.begin(), c.end(), greater<int>());

            for (int i = 0; i < col_size; ++i) {
                r = max(r, (i + 1) * c[i]);
            }
        }
      
        return r;
    }
};