Find the Maximum 2D Subarray

Geeks

Maximum size square sub-matrix with all 1s

Description:

Example:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  1  1  0
   1  1  1  1  1
   0  0  0  0  0

return 3*3=9

Idea:

因为update的过程，所以保证是square matrix。

1) Construct a sum matrix S[R][C] for the given M[R][C].
     a)    Copy first row and first columns as it is from M[][] to S[][]
     b)    For other entries, use following expressions to construct S[][]
         If M[i][j] is 1 then
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
         Else /*If M[i][j] is 0*/
            S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print 
   sub-matrix of M[][]

For the given M[R][C] in above example, constructed S[R][C] would be:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  0
   1  2  2  3  1
   0  0  0  0  0

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int threeMin(int a, int b, int c){
    return min(a, min(b, c));
}

int maxSquareSubarray(vector<vector<int>> matrix){

    int rowN=matrix.size();
    int columnN=matrix[0].size();

    vector<vector<int>> secondMatrix(rowN+1, vector<int>(columnN+1, 0));

    for(int i=0; i<rowN; i++){
        for(int j=0; j<columnN; j++){
            if (matrix[i][j] == 1)
                secondMatrix[i+1][j+1]=threeMin(secondMatrix[i][j], 
                                                secondMatrix[i+1][j], 
                                                secondMatrix[i][j+1])+1;
            else
                secondMatrix[i+1][j+1]=0;
        }
    }

    int maxArea=0;
    for(int i=0; i<rowN; i++){
        for(int j=0; j<columnN; j++){
            maxArea = max(maxArea, secondMatrix[i+1][j+1]);
        }
    }

    return maxArea*maxArea;
}

int main(){
    vector<vector<int>> matrix={ 
        {0,1,1,0,1},
        {1,1,0,1,0},
        {0,1,1,1,0},
        {1,1,1,1,0},
        {1,1,1,1,1},
        {0,0,0,0,0} };

        cout<<maxSquareSubarray(matrix);
}