[LC85]|Maximal Rectangle

store the left boundary, right boundary and height of the rectangle that contains the current point. The key point is to cumulatively calculate the boundaries and height.

matrix                left boundary              right boundary                   height
0 1 2 3 4 5 6        0 1 2 3 4 5 6                  0 1 2 3 4 5 6                           0 1 2 3 4 5 6
————-         ————                  ————-                           ————–

0 0 0 1 0 0 0       0 0 0 3 0 0 0                 7 7 7 4 7 7 7                         0 0 0 1 0 0 0
0 0 1 1 1 0 0         0 0 2 3 2 0 0                 7 7 5 4 5 7 7                          0 0 1 2 1 0 0
0 1 1 1 1 1 0           0 1 2 3 2 1 0                  7 6 5 4 5 6 7                          0 1 2 3 2 1 0

int[] left = new int[n];  // n is the number of columns
int[] right = new int[n];
int[] height = new int[n];

for each row:

// first update vector “left” from left to right
if (matrix[i][j] == ‘1’)
left[j] = max(left[j], cur_left);
else
left[j] = 0;
cur_left = j+1;

// second update vector “right” from right to left
if (matrix[i][j] == ‘1’)
right[j] = min(right[j], cur_right);
else
right[j] = n;
cur_right = j;

// third update vector “height” from either direction
if (matrix[i][j] == ‘1’)
height[j]++;
else
height[j] = 0;

// finally update the area covered by rows until now

max_area = max(max_area, (right[j] – left[j]) * height[j]);

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s