#TC = o(n)
#SC = o(n)
while True:
a = [int(k) for k in input().strip().split()]
if a[0]==0:
break
stack = []
max_area = 0
for k in range(1,len(a)): #a[0] is ignored as it is no of input elements
#if height greater than height of stack top. equal also falls in greater case acc to property given in drive description notes
if not stack or a[k]>=a[stack[-1]]:
stack.append(k)
#if less than
elif a[k]<a[stack[-1]]:
while stack and a[k]<a[stack[-1]]:
popped = stack.pop()
#if last element has been removed, then its left boundary should be 0 see drive pdf page 4 and test case 3 1 1 1 without this left boundary technique
if len(stack)==0:
left = 1 #because a[0] is no of elements we are considering 1 as first element
temp_area = a[popped] * (k-left)
else:
temp_area = a[popped] * (k-popped)
if temp_area>max_area:
max_area = temp_area
stack.append(k)
k += 1 #because after loop if range(1,5) => last k value will be 4, it will not increment to 5 before exiting
#if elements remaining in stack
while len(stack)!=0:
popped = stack.pop()
#if last element has been removed, then its left boundary should be 0 see drive pdf page 4 and test case 3 1 1 1 without this left boundary technique
if len(stack)==0:
left = 1 #because a[0] is no of elements we are considering 1 as first element
temp_area = a[popped] * (k-left)
else:
temp_area = a[popped] * (k-popped)
if temp_area>max_area:
max_area = temp_area
print(max_area)
I have tried a lot using multiple test cases as suggested by people. But I am still getting WA in SPOJ. Can you check the code or suggest some cases. In all public cases this is working fine.