You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
115 lines
2.6 KiB
C++
115 lines
2.6 KiB
C++
/*
|
|
* C++ Program to Find Largest Rectangular Area in a Histogram
|
|
*/
|
|
#include <iostream>
|
|
#include <cmath>
|
|
#include <climits>
|
|
#include <algorithm>
|
|
#define max(x, y, z) max(max(x, y) , z)
|
|
using namespace std;
|
|
/*
|
|
* get minimum of two numbers in hist[]
|
|
*/
|
|
int minVal(int *hist, int i, int j)
|
|
{
|
|
if (i == -1)
|
|
return j;
|
|
if (j == -1)
|
|
return i;
|
|
return (hist[i] < hist[j])? i : j;
|
|
}
|
|
/*
|
|
* get the middle index from corner indexes.
|
|
*/
|
|
int getMid(int s, int e)
|
|
{
|
|
return s + (e -s)/2;
|
|
}
|
|
|
|
/*
|
|
* get the index of minimum value in a given range of indexes.
|
|
*/
|
|
int RMQUtil(int *hist, int *st, int ss, int se, int qs, int qe, int index)
|
|
{
|
|
if (qs <= ss && qe >= se)
|
|
return st[index];
|
|
if (se < qs || ss > qe)
|
|
return -1;
|
|
int mid = getMid(ss, se);
|
|
return minVal(hist, RMQUtil(hist, st, ss, mid, qs, qe, 2 * index + 1),
|
|
RMQUtil(hist, st, mid + 1, se, qs, qe, 2 * index + 2));
|
|
}
|
|
/*
|
|
* Return index of minimum element in range from index qs to qe
|
|
*/
|
|
int RMQ(int *hist, int *st, int n, int qs, int qe)
|
|
{
|
|
if (qs < 0 || qe > n - 1 || qs > qe)
|
|
{
|
|
cout << "Invalid Input";
|
|
return -1;
|
|
}
|
|
return RMQUtil(hist, st, 0, n - 1, qs, qe, 0);
|
|
}
|
|
/*
|
|
* constructs Segment Tree for hist[ss..se].
|
|
*/
|
|
int constructSTUtil(int hist[], int ss, int se, int *st, int si)
|
|
{
|
|
if (ss == se)
|
|
return (st[si] = ss);
|
|
int mid = getMid(ss, se);
|
|
st[si] = minVal(hist, constructSTUtil(hist, ss, mid, st, si * 2 + 1),
|
|
constructSTUtil(hist, mid + 1, se, st, si * 2 + 2));
|
|
return st[si];
|
|
}
|
|
|
|
/*
|
|
* construct segment tree from given array.
|
|
*/
|
|
int *constructST(int hist[], int n)
|
|
{
|
|
int x = (int)(ceil(log2(n)));
|
|
int max_size = 2 * (int)pow(2, x) - 1;
|
|
int *st = new int[max_size];
|
|
constructSTUtil(hist, 0, n - 1, st, 0);
|
|
return st;
|
|
}
|
|
|
|
/*
|
|
* find the maximum rectangular area.
|
|
*/
|
|
int getMaxAreaRec(int *hist, int *st, int n, int l, int r)
|
|
{
|
|
if (l > r)
|
|
return INT_MIN;
|
|
if (l == r)
|
|
return hist[l];
|
|
int m = RMQ(hist, st, n, l, r);
|
|
return max (getMaxAreaRec(hist, st, n, l, m - 1),
|
|
getMaxAreaRec(hist, st, n, m + 1, r), (r - l + 1) * (hist[m]));
|
|
}
|
|
|
|
/*
|
|
* find max area
|
|
*/
|
|
int getMaxArea(int hist[], int n)
|
|
{
|
|
int *st = constructST(hist, n);
|
|
return getMaxAreaRec(hist, st, n, 0, n - 1);
|
|
}
|
|
|
|
/*
|
|
* Main
|
|
*/
|
|
int main()
|
|
{
|
|
int hist[] = {6, 1, 5, 4, 5, 2, 6};
|
|
int n = sizeof(hist)/sizeof(hist[0]);
|
|
cout << "Maximum area is " << getMaxArea(hist, n)<<endl;
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
|
|
Maximum area is 12
|