# coding exercise
We implement yet another way to print the area of the largest rectangle in a histogram of unit width heights. In addition to the simple approaches described in the previous posts, we look at recursive approach because there are overlapping solutions and iterative approaches using data structures
One approach is to use divide and conquer.
We can use the overlapping subproblems in terms of the areas computed between a range of indices. further if we can keep track of these indices and computations we dont have to redo them. This tecnique is called memoization. Here we don't compute the maxarea for a range that we have already computed and stored the value. So we keep track of ranges and the max area computed by the increasing order of start and end.Each time we update a range we update the start or end and the corresponding max value or both. How we choose the range of indices is our choice. The goal is to exhaust all the indexes in the histogram so that we don't leave out any portion. One idea here as it has appeared on geeks for geeks website is that we find the minimum value of the heights of bars in a histogram by dividing and conquering the entire range.
Given this minimum we find the max area as the maximum of the following :
1) Maximum area to the left
2) maximum area to the right
3) number of bars multiplied by minimum value
Note that the minimum in a range of bars does not guarantee the maximum area unless the same is applied for all ranges including the one bar that may shoot out of the chart.
Another way of choosing the indexes is to find it progressively to the right as we traverse range from start to end of indexes. In this method, The range that we have already covered, we have exhausted each bar as contributing to the final answer .
Yet another approach would be to divide and conquer the indexes and combine them so we calculate the max area of (a,b,c) as
Max (a, b, c ).
Specifically, given two bars in adjacent ranges, the area is the maximum of
1) minimum common height times number of bars in the combined range
2) maximum area of one range
3) maximum area of the other range.
If we chose the latter approach,
We keep track of the areas computed in the data structure discussed in memoization.
First without memoization, the solution is
Int MaxArea (ref int [] h, int start, int end, ref int min)
{
If (start == end)
{
min = h [start];
return min × 1;
}
If (start < end)
{
Int mid = (start + end)/2;
Int minleft = 0;
Int minright = 0;
Int left = MaxArea (c, ref h, start, mid, ref minleft);
Int right = MaxArea (c,ref h, mid +1, end, ref minright);
min = min (minleft, minright) ;
Int minArea= min × (end-start+1);
Return max (left,right, minArea);
}
Return 0;
}
