DP #19. Maximum size rectangle of all 1s. - mbhushan/dynpro GitHub Wiki
(19). Maximum size rectangle of all 1s.
Given a 2D matrix of 0s and 1s, find maximum size rectangle of all
1s in this matrix.
Maintain a temp array of same size as number of columns.
Copy first row to this temp array and find largest rectangular area
for histogram. Then keep adding elements of next row to this temp
array if they are not zero. If they are zero then put zero there.
Every time calculate max area in histogram.
MAX AREA IN HISTOGRAM.
* If stack is empty or A[index] >= stack.peek(), push *index* into stack.
* else keep popping from stack while A[stack.peek()] > A[index]
* While removing value from stack calculate area as follows:
Max Histogram Formula:
if (stack.isEmpty()) {
area = input[top] * i;
} else {
area = input[top] * (i - stack.peek() - 1)
}
maxArea = Math.max(maxArea, area);
|
c0 |
c1 |
c2 |
c3 |
c4 |
c5 |
|
|
|
|
|
|
|
Max Area (based on histogram area) |
| r0 |
1 |
0 |
0 |
1 |
1 |
1 |
sum(r0,r0) |
1 |
0 |
0 |
1 |
1 |
1 |
3 |
| r1 |
1 |
0 |
1 |
1 |
0 |
1 |
sum(r0,r1) |
1 |
0 |
1 |
2 |
0 |
2 |
2 |
| r2 |
0 |
1 |
1 |
1 |
1 |
1 |
sum(r0,r2) |
0 |
1 |
2 |
3 |
1 |
3 |
5 |
| r3 |
0 |
0 |
1 |
1 |
1 |
1 |
sum(r0,r3) |
0 |
0 |
3 |
4 |
2 |
4 |
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ans = 8 |
Max Rectangle of all 1s
- Time Complexity: (row * col)
- Space Complexity: O(row)