Find the largest rectangle can be possible in a given histogram. Assume the width of each bar is one unit.
or example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 2, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)
This problem is similar to finding max continuous sum in a given array of nos. Instead if finding the sum of nos, we need to max sum of array such that it will form a rectangle.
Algorithm.
1. Maintain following arrays
- result = which will hold the max area at that level
- height = height of the array which has the max area
- count = holds the no of bars combined together to give that area
2. At each iteration do following
if {Max previous area + current area} > {Current bar area}
Max area = {Max previous area + current area }
else
Max area = {Current bar area }
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <vector> | |
| using namespace std; | |
| int maxSquarAreaInHistorgram(int *arr, int size){ | |
| vector<int> result(size, 0); | |
| vector<int> heights(size,0); | |
| vector<int> count(size,0); | |
| if ( size == 0) | |
| return 0; | |
| result[0] = arr[0]; | |
| heights[0] = arr[0]; | |
| count[0] = 1; | |
| for (int i = 1; i < size; ++i){ | |
| int area=0; | |
| if ( arr[i] >= heights[i-1]){ | |
| area = (count[i-1]+1) * heights[i-1]; | |
| }else{ | |
| area = (count[i-1]+1) * arr[i]; | |
| } | |
| if ( area > arr[i]){ | |
| result[i] = area; | |
| heights[i] = heights[i-1]; | |
| count[i] = count[i] + 1; | |
| }else{ | |
| result[i] = arr[i]; | |
| heights[i] = arr[i]; | |
| count[i] = 1; | |
| } | |
| } | |
| return result[size-1]; | |
| } | |
| int main(int argc, char const *argv[]) { | |
| int histograms[] = {6, 2, 5, 4, 5, 2, 6}; | |
| cout << "Max Area: " << maxSquarAreaInHistorgram(histograms,sizeof(histograms)/sizeof(histograms[0])) << endl;; | |
| return 0; | |
| } |
CodeConnect