I am trying to solve maximum area on a histogram by divide and conquer. I understand how the RMQ works here. But I am not getting how the area function works.I found three conditions on geeks for geeks . According to geeksforgeeks-
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
Could anyone please explain how this idea works ? If I implement a n^2 solution then it check all possible range. But the method explained above check nlogn possibilities only.
For example- arr[] = {4,4,3,2,4}
Then the above methods only check the indixes(numbered from 1)-
1 to 5
5 to 5
6 to 5
5 to 4
1 to 3
4 to 3
1 to 2
2 to 2
3 to 2
2 to 1
1 to 0
To be more precise We’re never checking 1 to 4 , 2 to 4 , 3 to 3 etc.You can check a solution here Light OJ – 1083 – Histogram | Fall out, Codes!
How these methods eliminate these possibilities ? What’s the logic behind this ? Please anybody explain.