UVA 10074 - Take the Land

Maximum Rectangle Area by DP


Without Using STL

1)
#include <stdio.h>

int main() {
int m, n;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0)
break;
int i, j, k, map[100][100];
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
scanf("%d", &map[i][j]);
int max = 0, tmp, length, width;
for(i = 0; i < n; i++) {
int sum[100] = {};
for(j = i; j < n; j++) {
for(k = 0; k < m; k++) {
sum[k] += !map[j][k];
if(k == 0 || tmp != length*width)
tmp = 0, length = 0;
length++, width = j-i+1;
tmp += sum[k];
if(tmp == length*width)
max = max > tmp ? max : tmp;
}
}
}
printf("%d\n", max);
}
    return 0;
}

2)

#include<bits/stdc++.h>

using namespace std;

#define SM -1e5

int main()

{

    int n, m;

    int maxsum=0, csum=0;

    while(scanf("%d%d", &n, &m) && n!=0)

    {

        int mat[n+5][m+5], temp[n+5];

        for(int i=0; i<n; i++)

        {

            for(int j=0; j<m; j++)

            {

                scanf("%d", &mat[i][j]);

                if(mat[i][j]==1)

                    mat[i][j]=-109995;

                else mat[i][j]=1;

            }

        }

        int sum, csum, msum;

        sum=csum=msum=0;

        for(int k=0; k<m; k++)

        {

            memset(temp, 0, sizeof(temp));

            for(int j=k; j<m; j++)

            {

                for(int i=0; i<n; i++)

                    temp[i]+=mat[i][j];

                sum=csum=0;

                for(int i=0; i<n; i++) {

                    sum+=temp[i];

                    csum=max(sum, csum);

                    sum=max(sum, 0);

                }

                msum=max(csum, msum);

            }

        }

        printf("%d\n", msum);

    }

    return 0;

}

Using STL

#include<bits/stdc++.h>
using namespace std;
int R,C,A[105][105];
int maxHist(int row[])
{
    stack<int> result;
    int top_val;
    int max_area = 0;
    int area = 0;
    int i = 0;
    while (i < C)
    {
        if (result.empty() || row[result.top()] <= row[i])
            result.push(i++);
        else
        {
            top_val = row[result.top()];
            result.pop();
            area = top_val * i;

            if (!result.empty())
                area = top_val * (i - result.top() - 1 );
            max_area = max(area, max_area);
        }
    }
    while (!result.empty())
    {
        top_val = row[result.top()];
        result.pop();
        area = top_val * i;
        if (!result.empty())
            area = top_val * (i - result.top() - 1 );

        max_area = max(area, max_area);
    }
    return max_area;
}

int maxRectangle()
{
    int result = maxHist(A[0]);
    for (int i = 1; i < R; i++)
    {
        for (int j = 0; j < C; j++)
            if (A[i][j])
                A[i][j] += A[i - 1][j];
        result = max(result, maxHist(A[i]));
    }

    return result;
}
int main()
{
    while(cin>>R>>C)
    {
        if(R==0&&C==0)
            break;
        int i,j;
        for(i=0; i<R; i++)
        {
            for(j=0; j<C; j++)
            {
                cin>>A[i][j];
                if(A[i][j]==0)
                    A[i][j]=1;
                else
                    A[i][j]=0;
            }
        }
        cout<<maxRectangle()<<endl;
    }
    return 0;
}