HISTOGRA-SPOJ EXPLAINATION

Hello Guys,
Here today i am going to give an explaination to my code for HISTOGRA problem of SPOJ.

I used STACK datastructure to in my code.

TIME COMPLEXITY:O(N)

NOTE:This problem could be solved in O(NlogN).[I will be posting that code with explaination in my future posts]

ok now,lets go for the explaination part.

Here we have an array of integers , lets say from (0….n-1)

step 1:create an empty stack.

empty stack is created as   stack<datatype> s.

step 2:we traverse the elements from first element.

while traversing do the following steps.

if our stack is empty,push the respective index i of that element to stack.

if top element is  less than or equal to present element ,push that element to stack.

if top element is greater than present element,pop the top elements till the present element >= top elemnt

while popping,

if stack is empty : area=(popped element)*(i)

else                   :area=(popped element)*(i-top of stack-1)

when doing this operations,keep track of MAX value.

after all ,see if STACK is empty or not.

if STACK is still not empty

while stack is not empty :

if stack is not empty:

area=(popped element)*(i)

else                   :

area=(popped element)*(i-top of stack-1)

That’s it,now you have the MAX area.

Hope you enjoyed doing this problem.

Thank you.