Find the largest 2D subarray containing only 1's --- Dynamic Programming

Precedence of  Conditional operator ? : is from right to left.

Solution:
Hint: think how to change this problem to multiple problem of the largest rectangle under the skyline.

Simply think about each row as a x-axis, but what is the y-axis value of each row? For each column index in one row, it is the number of continuous 1' in that column above the row. Then for each row, we construct a skyline problem. solving it and compare each row, we can get this problem solution for O(NM), suppose N is the number of rows and M is the number of column.

Code:

int max2Dsubmatrix(const vector< vector > &A)
{
    vector > table; //record the skyline profile
    for(int i=0; i        for (int j=0; j    {
        if (A[i][j]!=0)
        {
            if(i-1 < 0) table[i][i] =1;
            else
                table[i][j] = table[i-1][j]+1;
        }
        else
            table[i][j]=0;
    }
    int max_rectange=0;
    for(const vector &t : table)
        max_rectange = max ( max_rectange, LargetRectangle(t));

    return max_rectange;
}