C++ Program to Find Largest Rectangular Area in a Histogram

«
»
This C++ Program Finds the Largest Rectangular Area in a Histogram.

Here is source code of the C++ Program to Find the Largest Rectangular Area in a Histogram. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* 
  2.  * C++ Program to Find Largest Rectangular Area in a Histogram
  3.  */
  4. #include <iostream>
  5. #include <cmath>
  6. #include <climits>
  7. #include <algorithm>
  8. #define max(x, y, z) max(max(x, y) , z)
  9. using namespace std;
  10. /* 
  11.  * get minimum of two numbers in hist[]
  12.  */ 
  13. int minVal(int *hist, int i, int j)
  14. {
  15.     if (i == -1) 
  16.         return j;
  17.     if (j == -1) 
  18.         return i;
  19.     return (hist[i] < hist[j])? i : j;
  20. }
  21. /* 
  22.  * get the middle index from corner indexes.
  23.  */  
  24. int getMid(int s, int e)
  25. {   
  26.     return s + (e -s)/2; 
  27. }
  28.  
  29. /*  
  30.  * get the index of minimum value in a given range of indexes. 
  31.  */
  32. int RMQUtil(int *hist, int *st, int ss, int se, int qs, int qe, int index)
  33. {
  34.     if (qs <= ss && qe >= se)
  35.         return st[index];
  36.     if (se < qs || ss > qe)
  37.         return -1;
  38.     int mid = getMid(ss, se);
  39.     return minVal(hist, RMQUtil(hist, st, ss, mid, qs, qe, 2 * index + 1),
  40.                   RMQUtil(hist, st, mid + 1, se, qs, qe, 2 * index + 2));
  41. }
  42. /*  
  43.  * Return index of minimum element in range from index qs to qe 
  44.  */
  45. int RMQ(int *hist, int *st, int n, int qs, int qe)
  46. {
  47.     if (qs < 0 || qe > n - 1 || qs > qe)
  48.     {
  49.         cout << "Invalid Input";
  50.         return -1;
  51.     }
  52.     return RMQUtil(hist, st, 0, n - 1, qs, qe, 0);
  53. }
  54. /*  
  55.  * constructs Segment Tree for hist[ss..se].
  56.  */
  57. int constructSTUtil(int hist[], int ss, int se, int *st, int si)
  58. {
  59.     if (ss == se)
  60.        return (st[si] = ss);
  61.     int mid = getMid(ss, se);
  62.     st[si] =  minVal(hist, constructSTUtil(hist, ss, mid, st, si * 2 + 1),
  63.                      constructSTUtil(hist, mid + 1, se, st, si * 2 + 2));
  64.     return st[si];
  65. }
  66.  
  67. /* 
  68.  * construct segment tree from given array. 
  69.  */
  70. int *constructST(int hist[], int n)
  71. {
  72.     int x = (int)(ceil(log2(n))); 
  73.     int max_size = 2 * (int)pow(2, x) - 1;
  74.     int *st = new int[max_size];
  75.     constructSTUtil(hist, 0, n - 1, st, 0);
  76.     return st;
  77. }
  78.  
  79. /* 
  80.  * find the maximum rectangular area.
  81.  */
  82. int getMaxAreaRec(int *hist, int *st, int n, int l, int r)
  83. {
  84.     if (l > r) 
  85.         return INT_MIN;
  86.     if (l == r)  
  87.         return hist[l];
  88.     int m = RMQ(hist, st, n, l, r);
  89.     return max (getMaxAreaRec(hist, st, n, l, m - 1), 
  90.                 getMaxAreaRec(hist, st, n, m + 1, r), (r - l + 1) * (hist[m]));
  91. }
  92.  
  93. /* 
  94.  * find max area
  95.  */
  96. int getMaxArea(int hist[], int n)
  97. {
  98.     int *st = constructST(hist, n);
  99.     return getMaxAreaRec(hist, st, n, 0, n - 1);
  100. }
  101.  
  102. /* 
  103.  * Main
  104.  */
  105. int main()
  106. {
  107.     int hist[] =  {6, 1, 5, 4, 5, 2, 6};
  108.     int n = sizeof(hist)/sizeof(hist[0]);
  109.     cout << "Maximum area is " << getMaxArea(hist, n)<<endl;
  110.     return 0;
  111. }

$ g++ largest_rectarea.cpp
$ a.out
 
Maximum area is 12
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.