here's an algorithm that can find the the max black rectangle in O(n^3)
here sum[i][j] is the number of contiguous 1s in the ith row from j column
until the end of the row
for (i=0;i<n;i++){
sum[i][m]=0;
for (j=m-1;j>=0;j--){
if (a[i][j]==1)
sum[i][j]=1+sum[i][j+1];
else
sum[i][j]=0;
}
}
so now sum[][] tells us how far we can go on this row
we can check for each possible height for each cell what would be the
maximum rectangle
res=0;
for (i=0;i<n;i++){
for (j=0;j<m;j++){
len=sum[i][j];
for (k=0;k+i<n;k++){
len=min(len,sum[k+i][j]); // the maximum width is the minimum possible width
among the rows
res=max(res,(k+1)*len); // k+1 is the height of rectangle and len is it's
width
}
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
