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. }

advertisement
$ 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
If you wish to look at all C++ Programming examples, go to C++ Programs.

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!
advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn