Largest Rectangular Area in a Histogram | Set 1 | GeeksforGeeks

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.

We can use Divide and Conquer to solve this in O(nLogn) time. The idea is to find the minimum value in the given array. Once we have index of the minimum value, the max area is maximum of following three values.
a) Maximum area in left side of minimum value (Not including the min value)
b) Maximum area in right side of minimum value (Not including the min value)
c) Number of bars multiplied by minimum value.

How to find the minimum efficiently? Range Minimum Query using Segment Tree can be used for this. We build segment tree of the given histogram heights. Once the segment tree is built, all range minimum queries take O(Logn) time. So over all complexity of the algorithm becomes.

Overall Time = Time to build Segment Tree + Time to recursively find maximum area

Time to build segment tree is O(n). Let the time to recursively find max area be T(n). It can be written as following.
T(n) = O(Logn) + T(n-1)
The solution of above recurrence is O(nLogn). 

// A recursive function to find the maximum rectangular area.

// It uses segment tree 'st' to find the minimum value in hist[l..r]

int getMaxAreaRec(int *hist, int *st, int n, int l, int r)

{

    // Base cases

    if (l > r)  return INT_MIN;

    if (l == r)  return hist[l];

    // Find index of the minimum value in given range

    // This takes O(Logn)time

    int m = RMQ(hist, st, n, l, r);

    /* Return maximum of following three possible cases

       a) Maximum area in Left of min value (not including the min)

       a) Maximum area in right of min value (not including the min)

       c) Maximum area including min */

    return max(getMaxAreaRec(hist, st, n, l, m-1),

               getMaxAreaRec(hist, st, n, m+1, r),

               (r-l+1)*(hist[m]) );

}

 

// The main function to find max area

int getMaxArea(int hist[], int n)

{

    // Build segment tree from given array. This takes

    // O(n) time

    int *st = constructST(hist, n);

    // Use recursive utility function to find the

    // maximum area

    return getMaxAreaRec(hist, st, n, 0, n-1);

}

Read full article from Largest Rectangular Area in a Histogram | Set 1 | GeeksforGeeks