Since I couldn't solve the problem myself, I read up the concept and codes and managed to get it submitted via a Divide and Conquer (divide from middle) approach and a stack based O(n) solution. I also came up with a segment tree solution but it seems to be giving me a wrong answer. I've referred to different segment tree solutions but can't seem to fix mine. Can anyone check out my approach and tell me what's wrong here? (It gives me correct answer on the test cases provided) Thanks! asked 15 Mar '17, 22:59

@epsilonalpha: You are getting WA because your approach is not right. Though you are finding out minimum number in the range using your query function, but you are not considering that number. I mean that you are using divide and conquer directly by dividing the array from the middle. Instead of this, you need to select the index of the minimum number that you are finding as middle index and then divide the array from that index. I am giving you a example that why your approach is not right. Consider the following array of heights and visit below link to see a photo describing how your query function is working. Array: [2 3 3 1] According to your solution, the array range [0,2] will never be considered which is indeed the correct answer. In a photo, The blocks in the merging are showing the answer in that range. Visit this link given by @akshaym_96 for the correct solution using divide and conquer. answered 17 Mar '17, 15:50

http://www.geeksforgeeks.org/largestrectangleunderhistogram/ and http://www.geeksforgeeks.org/largestrectangularareainahistogramset1/ will be handy!! answered 15 Mar '17, 23:27
I've already tried reading those and I still couldn't get my segment tree solution accepted.
(17 Mar '17, 03:35)

See this code. It's and simple and no need of segment tree answered 15 Mar '17, 23:11
I have got the code submitted via two different methods including the stack based approach you just gave link to, I just need to submit it via a segment tree once. I can't figure out my mistake.
(17 Mar '17, 03:36)

The problem has been solved. Here's the AC solution using Segment Trees for anyone needing this in future. http://ideone.com/H6LYjx answered 17 Mar '17, 20:06

https://ideone.com/gRTOfr why does my code gives Time limit exceed error all the time ... i have used the stack approach to solve the problem. answered 25 Mar, 02:03
