# 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)

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