程式語言 - 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

解答： 

int max(int a, int b)
{
    return a > b ? a: b;
}

int mysort(const void *a, const void *b)
{
    return ((*(int *)b) - (*(int *)a)); 
}

int largestSubmatrix(int** matrix, int matrixSize, int* matrixColSize)
{
    int i = 0;
    int j = 0;
    int r = 0;
    int row_size = matrixSize;
    int col_size = matrixColSize[0];

    for (i = 1; i < row_size; i++) {
        for (j = 0; j < col_size; j++) {
            if (matrix[i][j]) {
                matrix[i][j] = matrix[i - 1][j] + 1;
            }
        }
    }

    for (i = 0; i < row_size; i++) {
        qsort(&matrix[i][0], col_size, sizeof(int), mysort);

        for (j = 0; j < col_size; j++) {
            r = max(r, (j + 1) * matrix[i][j]);
        }
    }

    return r;
}