[85] Maximal Rectangle

跟前一題類似, 但是找正方形改成找矩形,
變很難
半放棄狀態
背答案要緊 囧

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

int min(int a, int b){
    return (a<b)? a: b;
}
int maximalRectangle(char** matrix, int matrixRowSize, int matrixColSize) {
    if (matrixRowSize < 1 || matrixColSize < 1)
        return 0;
//    printf("%d x %d\n",matrixRowSize,matrixColSize);
    int height[matrixColSize];
    int left[matrixColSize];
    int right[matrixColSize];
    memset(height,0, sizeof(int)*matrixColSize);
    memset(left,0, sizeof(int)*matrixColSize);

    int i,j, area=0;
#if 1
    for (i=0;i<matrixColSize; i++)
    {
        right[i]= matrixColSize;
    }
#endif
    for (i=0;i<matrixRowSize; i++)
    {
        int tmpleft = 0;
        int tmpright = matrixColSize;

        for (j=matrixColSize-1; j>=0;j--)
        {
            matrix[i][j] = matrix[i][j] -'0';

       
            if (matrix[i][j]==1)
            {
                right[j] = min(right[j],tmpright);
            }
            else
            {  
                right[j] = matrixColSize;
                tmpright = j;
            }          
        }

        for (j=0;j<matrixColSize;j++)
        {

            if (matrix[i][j]==1)
            {
                height[j] = height[j] +1;
                left[j] = max(tmpleft, left[j]);
            }
            else
            {  
                height[j] = 0;
                left[j] = 0;
                tmpleft = j+1;
            }          

            int new = (right[j]-left[j])*height[j];
            if(new > area)
                area = new;

        }
    }
    return area;
}