Geek wants to make a special space for candies on his bookshelf. Currently, it has N books, each of whose height is represented by the array height[] and has unit width.
Help him select 2 books such that he can store maximum candies between them by removing all the other books from between the selected books. The task is to find out the area between two books that can hold the maximum candies without changing the original position of selected books. 
Example 1:
Input: N = 3, height[] = {1, 3, 4}
Output: 1
Explanation:
1. Area between book of height 1 and book of 
height 3 is 0 as there is no space between 
them.
2. Area between book of height 1 and book of 
height 4 is 1 by removing book of height 3.
3. Area between book of height 3 and book of 
height 4 is 0 as there is no space between them.
Example 2:
Input: N = 6, height[] = {2, 1, 3, 4, 6, 5}
Output: 8
Explanation: Remove the 4 books in the middle 
creating length = 4 for the candy dam. Height 
for dam will be min(2,5) = 2. 
Area between book of height 2 and book 
of height 5 is 2 x 4 = 8.
Your Task:  
You don't need to read input or print anything. Complete the function maxCandy() which takes the array height[] and size of array N as input parameters and returns the maximum candies geek can store
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ height[i] ≤ 10^{5}

Difficulty: MEDIUM
Tags: Amortized analysis
Skill types: Amortized analysis
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

#Back-end complete function Template for Python 3

 
class Solution:
    def maxCandy(self, height, n): 
        # Your code goes here


Solutions:
class Solution:

	def maxCandy(self, height, n):
		(s, e) = (0, n - 1)
		res = 0
		while s < e:
			res = max(res, min(height[s], height[e]) * (e - s - 1))
			if height[s] < height[e]:
				s += 1
			else:
				e -= 1
		return res


class Solution:

	def maxCandy(self, height, n):
		i = 0
		j = n - 1
		max1 = 0
		while i < j:
			max1 = max((j - i - 1) * min(height[i], height[j]), max1)
			if height[i] < height[j]:
				i += 1
			elif height[i] > height[j]:
				j -= 1
			elif height[i] == height[j]:
				if height[i + 1] > height[j - 1]:
					i = i + 1
				else:
					j = j - 1
		return max1


class Solution:

	def maxCandy(self, a, n):
		(i, j) = (0, n - 1)
		ans = 0
		while j > i:
			if a[j] >= a[i]:
				ans = max(ans, a[i] * (j - i - 1))
				i = i + 1
				continue
			if a[i] > a[j]:
				ans = max(ans, a[j] * (j - i - 1))
				j = j - 1
				continue
		return ans


class Solution:

	def maxCandy(self, height, n):
		i = 0
		j = len(height) - 1
		maxi = 0
		while i < j:
			if height[i] <= height[j]:
				area = (j - i - 1) * height[i]
				maxi = max(maxi, area)
				i = i + 1
			elif height[i] > height[j]:
				area = (j - i - 1) * height[j]
				maxi = max(maxi, area)
				j = j - 1
		return maxi


class Solution:

	def maxCandy(self, height, n):
		ans = 0
		l = 0
		r = n - 1
		while l < r:
			area = min(height[r], height[l]) * (r - l - 1)
			ans = max(ans, area)
			if height[l] < height[r]:
				l += 1
			else:
				r -= 1
		return ans


class Solution:

	def maxCandy(self, height, n):
		if n == 1:
			return 0
		output = min(height[0], height[-1]) * (n - 2)
		i = -1
		while i < n - 1:
			i += 1
			output = max(output, min(height[i], height[-1]) * (n - i - 2))
			while i < n - 1 and height[-1] <= height[i]:
				height.pop()
				n -= 1
				output = max(output, min(height[i], height[-1]) * (n - i - 2))
		return output


class Solution:

	def maxCandy(self, height, n):
		if n == 1 or n == 2:
			return 0
		res = -1
		(l, r) = (0, n - 1)
		while l < r:
			res = max(res, min(height[l], height[r]) * (r - l - 1))
			if height[l] < height[r]:
				l += 1
			else:
				r -= 1
		return res


class Solution:

	def maxCandy(self, height, n):
		start = 0
		end = n - 1
		store = 0
		maxi = 0
		while start < end:
			store = min(height[start], height[end]) * (end - start - 1)
			maxi = max(maxi, store)
			if height[start] < height[end]:
				start += 1
			else:
				end -= 1
		return maxi


class Solution:

	def maxCandy(self, height, n):
		h = height
		if n < 3:
			return 0
		p = 0
		q = n - 1
		a = 0
		m = (n - 2) * min(h[0], h[n - 1])
		while p < q:
			a = min(h[p], h[q]) * (q - p - 1)
			m = max(a, m)
			if h[p] < h[q]:
				p += 1
			else:
				q -= 1
		return m


class Solution:

	def maxCandy(self, height, n):
		(result, left, right) = (0, 0, n - 1)
		while left < right:
			result = max(result, (right - left - 1) * min(height[left], height[right]))
			if height[left] < height[right]:
				left += 1
			else:
				right -= 1
		return result


class Solution:

	def maxCandy(self, height, n):
		maxcandy = 0
		i = 0
		j = len(height) - 1
		while i < j:
			maxcandy = max(maxcandy, min(height[i], height[j]) * (j - i - 1))
			if height[i] > height[j]:
				j -= 1
			else:
				i += 1
		return maxcandy


class Solution:

	def maxCandy(self, height, n):
		start = 0
		end = n - 1
		space = 0
		while start < end:
			hight = min(height[start], height[end])
			width = end - start - 1
			volume = hight * width
			space = max(space, volume)
			if height[start] <= height[end]:
				start += 1
			else:
				end -= 1
		return space


class Solution:

	def maxCandy(self, height, n):
		i = 0
		j = n - 1
		ans = 0
		y = 0
		while i < j:
			y = min(height[i], height[j])
			ans = max(ans, (j - i - 1) * y)
			if y == height[i]:
				i += 1
			else:
				j -= 1
		return ans


class Solution:

	def maxCandy(self, height, n):
		s = 0
		e = n
		res = 0
		while s < e:
			if res < (e - s - 2) * min(height[s], height[e - 1]):
				res = (e - s - 2) * min(height[s], height[e - 1])
			elif height[s] <= height[e - 1]:
				s += 1
			elif height[s] >= height[e - 1]:
				e -= 1
		return res


class Solution:

	def maxCandy(self, height, n):
		(left, right) = (0, len(height) - 1)
		area = 0
		b = 0
		length = 0
		while left < right:
			length = right - left - 1
			b = min(height[right], height[left])
			area = max(area, length * b)
			if height[left] < height[right]:
				left += 1
			else:
				right -= 1
		return area


class Solution:

	def maxCandy(self, A, N):
		ans = 0
		(i, j) = (0, N - 1)
		while j - i > 1:
			ans = max(ans, (j - i - 1) * min(A[i], A[j]))
			if A[i] <= A[j]:
				i += 1
			else:
				j -= 1
		return ans


class Solution:

	def maxCandy(self, height, n):
		max_candies_stored = 0
		no_of_books = len(height)
		start = 0
		end = no_of_books - 1
		while start < end:
			max_candies_stored = max(max_candies_stored, min(height[end], height[start]) * (end - start - 1))
			if height[end] < height[start]:
				end -= 1
			else:
				start += 1
		return max_candies_stored


class Solution:

	def maxCandy(self, height, n):
		j = n - 1
		i = 0
		a = height
		ans = 0
		res = 0
		while i < j:
			ans = (j - i - 1) * min(a[i], a[j])
			if ans > res:
				res = ans
			if a[i] > a[j]:
				j -= 1
			else:
				i += 1
		return res


class Solution:

	def maxCandy(self, height, n):
		i = 0
		j = n - 1
		d = 0
		while i < j:
			g = (j - i - 1) * min(height[i], height[j])
			if height[i] > height[j]:
				j -= 1
			else:
				i += 1
			if g > d:
				d = g
		return d


class Solution:

	def maxCandy(self, arr, n):
		start = 0
		end = n - 1
		if n == 1:
			return 0
		res = float('-inf')
		while start <= end:
			if arr[start] > arr[end]:
				res = max(res, arr[end] * (end - start - 1))
				end -= 1
			else:
				res = max(res, arr[start] * (end - start - 1))
				start += 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		print(obj.maxCandy(arr, n))


class Solution:

	def maxCandy(self, height, n):
		a = height
		n = len(a)
		left = 0
		right = n - 1
		area = 0
		while left < right:
			area = max(area, (right - left - 1) * min(a[left], a[right]))
			if a[left] < a[right]:
				left = left + 1
			elif a[left] > a[right]:
				right = right - 1
			else:
				left = left + 1
				right = right - 1
		return area
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		print(obj.maxCandy(arr, n))


class Solution:

	def maxCandy(self, height, n):
		i = 0
		j = n - 1
		maxi = 0
		while i < j:
			x = min(height[i], height[j])
			maxi = max(maxi, x * (j - i - 1))
			if height[i] > height[j]:
				j -= 1
			else:
				i += 1
		return maxi
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		print(obj.maxCandy(arr, n))


class Solution:

	def maxCandy(self, height, n):
		ans = 0
		if n <= 2:
			return 0
		low = 0
		high = n - 1
		while low < high:
			length = high - low - 1
			candy = length * min(arr[low], arr[high])
			if candy > ans:
				ans = candy
			if arr[low] <= arr[high]:
				low += 1
			else:
				high -= 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		print(obj.maxCandy(arr, n))


class Solution:

	def maxCandy(self, height, n):
		if n <= 2:
			return 0
		ans = 0
		i = 0
		j = n - 1
		while i < j:
			if height[i] < height[j]:
				ans = max(ans, height[i] * (j - i - 1))
				i += 1
			if height[i] > height[j]:
				ans = max(ans, height[j] * (j - i - 1))
				j -= 1
			if height[i] == height[j]:
				ans = max(ans, height[i] * (j - i - 1))
				i += 1
				j -= 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		print(obj.maxCandy(arr, n))


class Solution:

	def maxCandy(self, ht, n):
		(s, e, area) = (0, n - 1, 0)
		while s < e:
			area = max(area, (e - s - 1) * min(ht[s], ht[e]))
			if ht[s] < ht[e]:
				s += 1
			else:
				e -= 1
		return area


class Solution:

	def maxCandy(self, height, n):
		if len(height) <= 2:
			return 0
		i = 0
		j = n - 1
		ans = 0
		while i < j:
			maxh = min(height[i], height[j])
			gap = maxh * (j - i - 1)
			ans = max(ans, gap)
			if height[i] > height[j]:
				j -= 1
			else:
				i += 1
		return ans


class Solution:

	def maxCandy(self, height, n):
		start = 0
		end = n - 1
		ans = 0
		temp = 0
		while start < end:
			smallest = min(height[start], height[end])
			temp = smallest * (end - start - 1)
			if temp > ans:
				ans = temp
			if height[start] < height[end]:
				start += 1
			else:
				end -= 1
		return ans


class Solution:

	def maxCandy(self, height, n):
		start = 0
		end = n - 1
		res = 0
		while start < end:
			mini = min(height[start], height[end])
			area = (end - start - 1) * mini
			if res < area:
				res = area
			if height[start] < height[end]:
				start += 1
			else:
				end -= 1
		return res


class Solution:

	def maxCandy(self, a, n):
		i = 0
		j = n - 1
		ans = 0
		while i < j:
			if a[i] > a[j]:
				ans = max(ans, a[j] * (j - i - 1))
				j -= 1
			elif a[i] < a[j]:
				ans = max(ans, a[i] * (j - i - 1))
				i += 1
			else:
				ans = max(ans, a[j] * (j - i - 1))
				i += 1
				j -= 1
		return ans


class Solution:

	def maxCandy(self, height, n):
		start = 0
		end = n - 1
		global_sum = 0
		while start < end:
			local_sum = 0
			local_sum = min(height[start], height[end]) * (end - start - 1)
			global_sum = max(global_sum, local_sum)
			if height[start] < height[end]:
				start += 1
			else:
				end -= 1
		return global_sum


class Solution:

	def maxCandy(self, height, n):
		i = 0
		j = len(height) - 1
		a = 0
		s = 0
		while i < j:
			if height[i] == height[j]:
				s = height[i] * (j - i - 1)
				i += 1
				j -= 1
			elif height[i] < height[j]:
				s = height[i] * (j - i - 1)
				i += 1
			else:
				s = height[j] * (j - i - 1)
				j -= 1
			if a < s:
				a = s
		return a


class Solution:

	def maxCandy(self, ht, n):
		i = 0
		j = n - 1
		mx = 0
		while i < j:
			mx = max(mx, min(ht[i], ht[j]) * (j - i - 1))
			if ht[i] < ht[j]:
				i += 1
			elif ht[i] > ht[j]:
				j -= 1
			else:
				i += 1
				j -= 1
		return mx


import sys

class Solution:

	def maxCandy(self, height, n):
		i = 0
		j = n - 1
		max_area = 0
		while i < j:
			sml = min(height[i], height[j])
			area = sml * (j - i - 1)
			if max_area < area:
				max_area = area
			if height[i] < height[j]:
				i += 1
			else:
				j -= 1
		return max_area


class Solution:

	def maxCandy(self, height, n):
		s = 0
		e = n - 1
		ans = 0
		while s < e:
			b = e - s - 1
			l = min(height[s], height[e])
			area = l * b
			ans = max(ans, area)
			if height[s] < height[e]:
				s += 1
			else:
				e -= 1
		return ans


class Solution:

	def maxCandy(self, height, n):

		def calc(p, q, r):
			l = min(p, q)
			b = r
			return max(ans, l * b)
		s = 0
		e = n - 1
		ans = 0
		while s < e:
			b = e - s - 1
			area = calc(height[s], height[e], b)
			ans = max(ans, area)
			if height[s] < height[e]:
				s += 1
			else:
				e -= 1
		return ans


class Solution:

	def maxCandy(self, height, n):
		if n == 1 or n == 2:
			return 0
		front = 0
		tail = n - 1
		ans = 0
		while front < tail:
			ans = max(ans, (tail - front - 1) * min(height[front], height[tail]))
			if height[front] > height[tail]:
				tail -= 1
			elif height[front] < height[tail]:
				front += 1
			else:
				front += 1
				tail -= 1
		return ans


class Solution:

	def maxCandy(self, height, n):
		i = 0
		mc = 0
		j = n - 1
		while i < j:
			if height[i] < height[j]:
				mc = max(mc, (j - i - 1) * height[i])
				i = i + 1
			else:
				mc = max(mc, (j - i - 1) * height[j])
				j = j - 1
		return mc


class Solution:

	def maxCandy(self, height, n):
		l = 0
		h = n - 1
		res = 0
		while l < h:
			res = max(res, min(height[l], height[h]) * (h - l - 1))
			if height[l] < height[h]:
				l += 1
			elif height[l] > height[h]:
				h -= 1
			else:
				l += 1
				h -= 1
		return res


class Solution:

	def maxCandy(self, l, n):
		ans = 0
		(i, j) = (0, n - 1)
		while i < j:
			if l[i] < l[j]:
				ans = max(ans, (j - i - 1) * l[i])
				i += 1
			if l[i] > l[j]:
				ans = max(ans, (j - i - 1) * l[j])
				j -= 1
			if l[i] == l[j]:
				ans = max(ans, (j - i - 1) * l[i])
				i += 1
				j -= 1
		return ans