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;
}
