Given an array Arr[] that contains N integers (may be positive, negative or zero). Find the product of the maximum product subarray.
Example 1:
Input:
N = 5
Arr[] = {6, -3, -10, 0, 2}
Output: 180
Explanation: Subarray with maximum product
is [6, -3, -10] which gives product as 180.
Example 2:
Input:
N = 6
Arr[] = {2, 3, 4, 5, -1, 0}
Output: 120
Explanation: Subarray with maximum product
is [2, 3, 4, 5] which gives product as 120.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxProduct() which takes the array of integers arr and n as parameters and returns an integer denoting the answer.
Note: Use 64-bit integer data type to avoid overflow.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 500
-10^{2} ≤ Arr_{i} ≤ 10^{2}

Difficulty: MEDIUM
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3
class Solution:

	# Function to find maximum
	# product subarray
	def maxProduct(self,arr, n):
		# code here

Solutions:
class Solution:

	def maxProduct(self, arr, n):
		ans = arr[0]
		(ma, mi) = (ans, ans)
		for i in range(1, n):
			if arr[i] < 0:
				temp = ma
				ma = mi
				mi = temp
			ma = max(arr[i], ma * arr[i])
			mi = min(arr[i], mi * arr[i])
			ans = max(ans, ma)
		return ans


class Solution:

	def maxProduct(self, arr, n):
		maxi = -1000.0
		cur = 1
		for i in range(n):
			cur *= arr[i]
			if cur > maxi:
				maxi = cur
			if cur == 0:
				cur = 1
		cur = 1
		for i in range(n - 1, -1, -1):
			cur *= arr[i]
			if cur > maxi:
				maxi = cur
			if cur == 0:
				cur = 1
		return maxi


class Solution:

	def maxProduct(self, nums, n):
		(max_prod, min_prod, ans) = (nums[0], nums[0], nums[0])
		for i in range(1, len(nums)):
			x = max(nums[i], max_prod * nums[i], min_prod * nums[i])
			y = min(nums[i], max_prod * nums[i], min_prod * nums[i])
			(max_prod, min_prod) = (x, y)
			ans = max(max_prod, ans)
		return ans


class Solution:

	def maxProduct(self, arr, n):
		pre = 1
		suff = 1
		ans = -1000000000
		for i in range(len(arr)):
			if pre == 0:
				pre = 1
			if suff == 0:
				suff = 1
			pre = pre * arr[i]
			suff = suff * arr[n - i - 1]
			ans = max(ans, max(pre, suff))
		return ans


class Solution:

	def maxProduct(self, arr, n):
		max = arr[0]
		for i in range(n):
			c = arr[i]
			if arr[i] == 0:
				continue
			else:
				for j in range(i + 1, n):
					if arr[j] == 0:
						break
					else:
						c = c * arr[j]
						if max < c:
							max = c
				if max < c:
					max = c
		return max


class Solution:

	def maxProduct(self, arr, n):
		pre = 1
		suff = 1
		ans = float('-inf')
		for i in range(n):
			if pre == 0:
				pre = 1
			if suff == 0:
				suff = 1
			pre = pre * arr[i]
			suff = suff * arr[n - i - 1]
			ans = max(ans, max(pre, suff))
		return ans


class Solution:

	def maxProduct(self, arr, n):
		if n == 0:
			return 0
		max_product = arr[0]
		min_product = arr[0]
		max_so_far = arr[0]
		for i in range(1, n):
			curr = arr[i]
			temp_max = max(curr, max_product * curr, min_product * curr)
			min_product = min(curr, max_product * curr, min_product * curr)
			max_product = temp_max
			max_so_far = max(max_so_far, max_product)
		return max_so_far


class Solution:

	def maxProduct(self, arr, n):
		product = 1
		maxi = arr[0]
		for i in range(n):
			product *= arr[i]
			maxi = max(maxi, product)
			if product == 0:
				product = 1
		product = 1
		for i in range(n - 1, -1, -1):
			product *= arr[i]
			maxi = max(maxi, product)
			if product == 0:
				product = 1
		return maxi


class Solution:

	def maxProduct(self, arr, n):
		(prefix, suffix, ans) = (1, 1, -(10 ** 9 + 7))
		for i in range(n):
			prefix *= arr[i]
			suffix *= arr[n - i - 1]
			ans = max(ans, max(prefix, suffix))
			if prefix == 0:
				prefix = 1
			if suffix == 0:
				suffix = 1
		return ans


class Solution:

	def maxProduct(self, nums, n):
		res = -10 ** 9
		prefix = 1
		suffix = 1
		for i in range(n):
			if prefix == 0:
				prefix = 1
			if suffix == 0:
				suffix = 1
			prefix = prefix * nums[i]
			suffix = suffix * nums[n - i - 1]
			res = max(res, max(prefix, suffix))
		return res


class Solution:

	def maxProduct(self, arr, n):
		mpp = arr[0]
		mnp = arr[0]
		ans = max(arr)
		for i in range(1, n):
			ans = max(ans, mpp * arr[i], mnp * arr[i])
			(mpp, mnp) = (max(arr[i], mpp * arr[i], mnp * arr[i], 0), min(arr[i], mnp * arr[i], mpp * arr[i], 0))
		return ans


class Solution:

	def maxProduct(self, arr, n):
		max_so_far = arr[0]
		max_end_here = arr[0]
		min_end_here = arr[0]
		for i in range(1, n):
			if arr[i] < 0:
				(max_end_here, min_end_here) = (min_end_here, max_end_here)
			min_end_here = min(arr[i], min_end_here * arr[i])
			max_end_here = max(arr[i], max_end_here * arr[i])
			max_so_far = max(max_so_far, max_end_here)
		return max_so_far


import sys

class Solution:

	def maxProduct(self, arr, n):
		frontprod = 1
		endprod = 1
		res = -sys.maxsize - 1
		for i in range(n):
			frontprod = frontprod * arr[i]
			if frontprod > res:
				res = frontprod
			if frontprod == 0:
				frontprod = 1
			endprod = endprod * arr[n - i - 1]
			if endprod > res:
				res = endprod
			if endprod == 0:
				endprod = 1
		return res


class Solution:

	def maxProduct(self, arr, n):
		pref = 1
		suf = 1
		j = 0
		max_ = arr[0]
		for i in range(n):
			if arr[i] != 0:
				pref *= arr[i]
				if pref > max_:
					max_ = pref
			else:
				pref = 1
			if arr[n - i - 1] != 0:
				suf *= arr[n - i - 1]
				if suf > max_:
					max_ = suf
			else:
				suf = 1
		return max_


class Solution:

	def maxProduct(self, arr, n):
		res = max(arr)
		(cmin, cmax) = (1, 1)
		for i in arr:
			if i == 0:
				(cmin, cmax) = (1, 1)
				continue
			temp = cmax * i
			cmax = max(cmax * i, cmin * i, i)
			cmin = min(temp, cmin * i, i)
			res = max(cmax, res)
		return res


class Solution:

	def maxProduct(self, arr, n):
		maxi = arr[0]
		mini = arr[0]
		ans = arr[0]
		for i in range(1, len(arr)):
			if arr[i] < 0:
				(mini, maxi) = (maxi, mini)
			maxi = max(arr[i], maxi * arr[i])
			mini = min(arr[i], mini * arr[i])
			if maxi > ans:
				ans = maxi
		return ans


class Solution:

	def maxProduct(self, arr, n):
		if not arr:
			return 0
		max_product = arr[0]
		min_product = arr[0]
		result = max_product
		for i in range(1, len(arr)):
			curr_num = arr[i]
			temp_max = max(curr_num, max_product * curr_num, min_product * curr_num)
			temp_min = min(curr_num, max_product * curr_num, min_product * curr_num)
			max_product = temp_max
			min_product = temp_min
			result = max(result, max_product)
		return result


class Solution:

	def maxProduct(self, arr, n):
		if n == 1:
			return arr[0]
		sm = 1
		ans = 0
		for i in arr:
			sm *= i
			ans = max(ans, sm)
			if sm == 0:
				sm = 1
		sm = 1
		for i in range(n - 1, 0, -1):
			sm *= arr[i]
			ans = max(ans, sm)
			if sm == 0:
				sm = 1
		return ans


class Solution:

	def maxProduct(self, arr, n):
		b = arr[::-1]
		a = arr
		for i in range(1, n):
			if a[i - 1] != 0:
				a[i] *= a[i - 1]
			if b[i - 1] != 0:
				b[i] *= b[i - 1]
		return max(a + b)


class Solution:

	def maxProduct(self, arr, n):
		prod = 1
		res = min(arr)
		for x in arr:
			prod = x * prod
			if prod > res:
				res = prod
			if prod == 0:
				prod = 1
		prod = 1
		for x in reversed(arr):
			prod = x * prod
			if prod > res:
				res = prod
			if prod == 0:
				prod = 1
		return res


class Solution:

	def maxProduct(self, arr, n):
		maximum = arr[0]
		prefix = 1
		suffix = 1
		for i in range(n):
			if prefix == 0:
				prefix = 1
			if suffix == 0:
				suffix = 1
			prefix *= arr[i]
			suffix *= arr[n - i - 1]
			maximum = max(maximum, prefix, suffix)
		return maximum


import sys

class Solution:

	def maxProduct(self, arr, n):
		prefix = 1
		suffix = 1
		res = -sys.maxsize - 1
		for i in range(n):
			prefix = prefix * arr[i]
			if prefix > res:
				res = prefix
			if prefix == 0:
				prefix = 1
			suffix = suffix * arr[n - i - 1]
			if suffix > res:
				res = suffix
			if suffix == 0:
				suffix = 1
		return res


class Solution:

	def maxProduct(self, arr, n):
		max_product = -1000000000.0
		product = 1
		for i in range(n):
			if arr[i] == 0:
				product = 1
				max_product = max(0, max_product)
			else:
				product *= arr[i]
				max_product = max(product, max_product)
		product = 1
		for i in range(n - 1, -1, -1):
			if arr[i] == 0:
				product = 1
				max_product = max(0, max_product)
			else:
				product *= arr[i]
				max_product = max(product, max_product)
		return max_product


from typing import List

class Solution:

	def maxProduct(self, nums, n):
		max_product = [0] * len(nums)
		min_product = [0] * len(nums)
		max_product[0] = min_product[0] = result = nums[0]
		for i in range(1, len(nums)):
			if nums[i] > 0:
				max_product[i] = max(nums[i], max_product[i - 1] * nums[i])
				min_product[i] = min(nums[i], min_product[i - 1] * nums[i])
			elif nums[i] < 0:
				max_product[i] = max(nums[i], min_product[i - 1] * nums[i])
				min_product[i] = min(nums[i], max_product[i - 1] * nums[i])
			else:
				max_product[i] = min_product[i] = 0
			result = max(result, max_product[i])
		return result


class Solution:

	def maxProduct(self, nums, n):
		(minValue, maxValue, cMax) = (nums[0], nums[0], nums[0])
		for num in nums[1:]:
			if num is 0:
				minValue = 1
				maxValue = 1
				cMax = max(cMax, num)
			minProduct = minValue * num
			maxProduct = maxValue * num
			minValue = min(num, minProduct, maxProduct)
			maxValue = max(num, minProduct, maxProduct)
			cMax = max(maxValue, cMax)
		return cMax


class Solution:

	def maxProduct(self, arr, n):
		prod1 = arr[0]
		prod2 = arr[0]
		res = arr[0]
		for i in range(1, n, 1):
			if arr[i] < 0:
				(prod1, prod2) = (prod2, prod1)
			prod1 = max(arr[i], prod1 * arr[i])
			prod2 = min(arr[i], prod2 * arr[i])
			res = max(res, prod1)
		return res


class Solution:

	def maxProduct(self, arr, n):
		currMax = currMin = 1
		maxProd = max(arr)
		for i in range(n):
			if arr[i] == 0:
				currMax = 1
				currMin = 1
				continue
			temp = arr[i] * currMax
			currMax = max(temp, arr[i] * currMin, arr[i])
			currMin = min(temp, arr[i] * currMin, arr[i])
			maxProd = max(maxProd, currMax)
		return maxProd


class Solution:

	def maxProduct(self, arr, n):
		min_temp = arr[0]
		max_temp = arr[0]
		max_value = arr[0]
		for i in range(1, n):
			if arr[i] < 0:
				(min_temp, max_temp) = (max_temp, min_temp)
			min_temp = min(arr[i], min_temp * arr[i])
			max_temp = max(arr[i], max_temp * arr[i])
			max_value = max(max_temp, max_value)
		return max_value


class Solution:

	def maxProduct(self, arr, size):
		curMax = curMin = 1
		res = arr[0]
		for n in arr:
			vals = (n, n * curMax, n * curMin)
			curMax = max(vals)
			curMin = min(vals)
			res = max(res, curMax)
		return res


class Solution:

	def maxProduct(self, arr, n):
		maxval = arr[0]
		minval = arr[0]
		maxprod = arr[0]
		for i in range(1, n, 1):
			if arr[i] < 0:
				(minval, maxval) = (maxval, minval)
			maxval = max(arr[i], maxval * arr[i])
			minval = min(arr[i], minval * arr[i])
			maxprod = max(maxval, maxprod)
		return maxprod


class Solution:

	def maxProduct(self, arr, n):
		minVal = arr[0]
		maxVal = arr[0]
		maxProduct = arr[0]
		for i in range(1, n, 1):
			if arr[i] < 0:
				temp = maxVal
				maxVal = minVal
				minVal = temp
			maxVal = max(arr[i], maxVal * arr[i])
			minVal = min(arr[i], minVal * arr[i])
			maxProduct = max(maxProduct, maxVal)
		return maxProduct


class Solution:

	def maxProduct(self, arr, n):
		max_so_far = arr[0]
		min_so_far = arr[0]
		result = arr[0]
		for i in range(1, n):
			temp_max = max(arr[i], max_so_far * arr[i], min_so_far * arr[i])
			temp_min = min(arr[i], max_so_far * arr[i], min_so_far * arr[i])
			max_so_far = temp_max
			min_so_far = temp_min
			result = max(result, max_so_far)
		return result


class Solution:

	def maxProduct(self, arr, n):
		(ans, maxtillnow, mintillnow) = (arr[0], arr[0], arr[0])
		for ele in arr[1:]:
			temp = max(ele, ele * maxtillnow, ele * mintillnow)
			mintillnow = min(ele, ele * maxtillnow, ele * mintillnow)
			maxtillnow = temp
			ans = max(ans, maxtillnow)
		return ans


class Solution:

	def maxProduct(self, arr, n):
		max_product = arr[0]
		min_product = arr[0]
		overall_max_product = arr[0]
		for i in range(1, n):
			if arr[i] < 0:
				(max_product, min_product) = (min_product, max_product)
			max_product = max(arr[i], max_product * arr[i])
			min_product = min(arr[i], min_product * arr[i])
			overall_max_product = max(overall_max_product, max_product)
		return overall_max_product


class Solution:

	def maxProduct(self, arr, n):
		res = max(arr)
		currmin = 1
		currmax = 1
		for n in arr:
			if n == 0:
				(currmin, currmax) = (1, 1)
				continue
			tmp = currmax * n
			currmax = max(n * currmax, n * currmin, n)
			currmin = min(tmp, n * currmin, n)
			res = max(res, currmax)
		return res


import sys

class Solution:

	def maxProduct(self, arr, n):
		pr = 1
		mspr = -sys.maxsize - 1
		for i in range(n):
			pr = pr * arr[i]
			mspr = max(mspr, pr)
			if arr[i] == 0:
				pr = 1
		pr = 1
		for i in range(n - 1, -1, -1):
			pr = pr * arr[i]
			mspr = max(mspr, pr)
			if arr[i] == 0:
				pr = 1
		return mspr


import sys
from sys import maxsize

class Solution:

	def maxProduct(self, arr, n):
		(ans, maxTillNow, minTillNow) = (max(arr), 1, 1)
		for i in arr:
			if i == 0:
				(maxTillNow, minTillNow) = (1, 1)
				continue
			temp = i * maxTillNow
			maxTillNow = max(i * maxTillNow, i * minTillNow, i)
			minTillNow = min(i * minTillNow, temp, i)
			ans = max(ans, maxTillNow)
		return ans


class Solution:

	def maxProduct(self, arr, n):
		maxpro = arr[0]
		p = 1
		for i in arr:
			p *= i
			maxpro = max(maxpro, p)
			if i == 0:
				p = 1
		p = 1
		for i in reversed(arr):
			p *= i
			maxpro = max(maxpro, p)
			if i == 0:
				p = 1
		return maxpro


class Solution(object):

	def maxProduct(self, nums, n):
		if not nums:
			return 0
		result = maxProduct = minProduct = nums[0]
		for num in nums[1:]:
			tempMaxProduct = max(num, num * maxProduct, num * minProduct)
			minProduct = min(num, num * maxProduct, num * minProduct)
			maxProduct = tempMaxProduct
			result = max(result, maxProduct)
		return result


class Solution:

	def maxProduct(self, arr, n):
		(maxP, minP, ans) = (arr[0], arr[0], arr[0])
		for i in range(1, n):
			(c1, c2) = (maxP * arr[i], minP * arr[i])
			(maxP, minP) = (max(max(c1, c2), arr[i]), min(min(c1, c2), arr[i]))
			ans = max(ans, maxP)
		return ans


class Solution:

	def maxProduct(self, nums, n):
		ans = arr[0]
		(maxx, minn) = (ans, ans)
		for i in range(1, n):
			if arr[i] < 0:
				var = maxx
				maxx = minn
				minn = var
			maxx = max(arr[i], maxx * arr[i])
			minn = min(arr[i], minn * arr[i])
			ans = max(ans, maxx)
		return ans


import sys

class Solution:

	def maxProduct(self, arr, n):
		p1 = arr[0]
		p2 = arr[0]
		maxi = arr[0]
		for i in range(1, n):
			temp = max(arr[i], p1 * arr[i], p2 * arr[i])
			p2 = min(arr[i], p1 * arr[i], p2 * arr[i])
			p1 = temp
			maxi = max(maxi, p1)
		return maxi


class Solution:

	def maxProduct(self, arr, n):
		max_product = 1
		min_product = 1
		res = max(arr)
		for i in arr:
			if i == 0:
				max_product = 1
				min_product = 1
				continue
			temp = i * max_product
			max_product = max(temp, i, min_product * i)
			min_product = min(i, min_product * i, temp)
			res = max(res, max_product, min_product)
		return res


class Solution:

	def maxProduct(self, arr, n):
		minToHere = [0] * n
		maxToHere = [0] * n
		minToHere[0] = arr[0]
		maxToHere[0] = arr[0]
		for i in range(1, n):
			v1 = arr[i] * minToHere[i - 1]
			v2 = arr[i] * maxToHere[i - 1]
			v3 = arr[i]
			maxToHere[i] = max([v1, v2, v3])
			minToHere[i] = min([v1, v2, v3])
		return max(maxToHere)


class Solution:

	def maxProduct(self, arr, n):
		dic = {}
		max1 = -10000000
		pr = 1
		for i in range(len(arr)):
			pr = pr * arr[i]
			if max1 < pr:
				max1 = pr
			if pr == 0:
				pr = 1
				dic.clear()
				continue
			for j in dic:
				pr1 = pr // dic[j]
				if max1 < pr1:
					max1 = pr1
			dic[i] = pr
		return max1


class Solution:

	def maxProduct(self, arr, n):
		maxxi = 0
		a = 0
		value = 0
		pehla = 0
		last = 0
		if len(arr) == 1:
			maxxi = arr[0]
		else:
			for i in range(0, len(arr)):
				if value == 0 and arr[i] < 0 and (i == len(arr) - 1):
					value = 0
				elif value == 0 and arr[i] < 0 and (arr[i + 1] == 0):
					value = 0
				else:
					if i == len(arr) - 1 and arr[i] != 0:
						if arr[i] > 0:
							if value == 0:
								value = 1
								value *= arr[i]
							else:
								value *= arr[i]
							last = last * arr[i]
						elif arr[i] < 0:
							if value == 0:
								value = 1
								value *= arr[i]
							else:
								value *= arr[i]
							if pehla == 0:
								pehla = value
							last = arr[i]
						if value > 0:
							if value > maxxi:
								maxxi = value
						elif value < 0:
							ww = max(pehla, last)
							if value // ww > maxxi:
								maxxi = value // ww
					if arr[i] > 0:
						if value == 0:
							value = 1
							value *= arr[i]
						else:
							value *= arr[i]
						last = last * arr[i]
					elif arr[i] < 0:
						if value == 0:
							value = 1
							value *= arr[i]
						else:
							value *= arr[i]
						if pehla == 0:
							pehla = value
						last = arr[i]
					else:
						if value > 0:
							if value > maxxi:
								maxxi = value
						elif value < 0:
							ww = max(pehla, last)
							if value // ww > maxxi:
								maxxi = value // ww
						value = 0
						pehla = 0
						last = 0
		return maxxi


class Solution:

	def maxProduct(self, arr, n):
		max_so_far = arr[0]
		max_ending_here = arr[0]
		min_ending_here = arr[0]
		for i in range(1, len(arr)):
			temp = max_ending_here
			max_ending_here = max(arr[i], max_ending_here * arr[i], min_ending_here * arr[i])
			min_ending_here = min(temp * arr[i], min_ending_here * arr[i], arr[i])
			max_so_far = max(max_so_far, max_ending_here)
		return max_so_far


class Solution:

	def maxProduct(self, arr, n):
		maxvalue = arr[0]
		minvalue = arr[0]
		maxproduct = arr[0]
		for i in range(1, n):
			if arr[i] < 0:
				temp = maxvalue
				maxvalue = minvalue
				minvalue = temp
			maxvalue = max(arr[i], maxvalue * arr[i])
			minvalue = min(arr[i], minvalue * arr[i])
			maxproduct = max(maxproduct, maxvalue)
		return maxproduct


class Solution:

	def maxProduct(self, arr, n):
		ans = -float('inf')
		minm = 1
		maxm = 1
		for x in arr:
			if x < 0:
				(maxm, minm) = (minm, maxm)
			maxm = max(maxm * x, x)
			minm = min(minm * x, x)
			ans = max(ans, maxm)
		return ans


class Solution:

	def maxProduct(self, arr, n):
		ans = -float('inf')
		minm = 1
		maxm = 1
		for x in arr:
			if x < 0:
				(maxm, minm) = (minm, maxm)
			maxm = max(maxm * x, x)
			minm = min(minm * x, x)
			ans = max(ans, maxm)
		return ans
		maxmVal = 1
		minmVal = 1
		maxm = -float('inf')
		for i in range(n):
			if arr[i] < 0:
				(maxmVal, minmVal) = (minmVal, maxmVal)
			maxmVal = max(arr[i], maxmVal * arr[i])
			minmVal = min(arr[i], minmVal * arr[i])
			maxm = max(maxm, maxmVal)
		return maxm
		totall = totalr = 1
		maxml = maxmr = -float('inf')
		l = []
		r = []
		for i in range(n):
			totall *= arr[i]
			totalr *= arr[n - i - 1]
			maxml = max(maxml, totall)
			maxmr = max(maxmr, totalr)
			l.append(maxml)
			r.append(maxmr)
			if totall == 0:
				totall = 1
			if totalr == 0:
				totalr = 1
		maxm = -float('inf')
		for i in range(n):
			maxm = max(maxm, l[i], r[i])
		return maxm
		maxm = -float('inf')
		total = 1
		neg = 1
		for x in arr:
			total = x * total
			maxm = max(maxm, total, total // neg)
			if total == 0:
				total = 1
				neg = 1
			if total < 0 and neg > 0:
				neg = total
		return maxm


class Solution:

	def maxProduct(self, arr, n):
		maxSoFar = arr[0]
		maxEndingHere = arr[0]
		minEndingHere = arr[0]
		for i in range(1, n):
			if arr[i] < 0:
				(maxEndingHere, minEndingHere) = (minEndingHere, maxEndingHere)
			maxEndingHere = max(arr[i], maxEndingHere * arr[i])
			minEndingHere = min(arr[i], minEndingHere * arr[i])
			maxSoFar = max(maxSoFar, maxEndingHere)
		return maxSoFar


class Solution:

	def maxProduct(self, arr, n):
		max_element = 1
		min_element = 1
		result = -float('inf')
		for i in range(n):
			x = max_element * arr[i]
			y = min_element * arr[i]
			max_element = max(x, y, arr[i])
			min_element = min(x, y, arr[i])
			result = max(max_element, result)
			if arr[i] == 0:
				min_element = 1
				max_element = 1
		return result


class Solution:

	def maxProduct(self, arr, n):
		ma = arr[0]
		mi = arr[0]
		res = arr[0]
		for e in arr[1:]:
			if e < 0:
				(ma, mi) = (mi, ma)
			ma = max(e, e * ma)
			mi = min(e, e * mi)
			res = max(res, ma)
		return res


class Solution:

	def maxProduct(self, arr, n):
		res = max(arr)
		(maxVal, minVal) = (1, 1)
		for (i, val) in enumerate(arr):
			(maxVal, minVal) = (max(val * maxVal, val * minVal, val), min(val * maxVal, val * minVal, val))
			res = max(res, maxVal, minVal)
		return res


class Solution:

	def maxProduct(self, nums, n):
		mx = 1
		mn = 1
		result = max(nums)
		for i in range(n):
			temp = mx * nums[i]
			mx = max(mx * nums[i], mn * nums[i], nums[i])
			mn = min(temp, mn * nums[i], nums[i])
			result = max(result, mx)
		return result


class Solution:

	def maxProduct(self, arr, n):
		curr_prod = 1
		max_prod = float('-inf')
		for i in arr:
			curr_prod *= i
			max_prod = max(max_prod, curr_prod)
			if curr_prod == 0:
				curr_prod = 1
		curr_prod = 1
		for i in range(n - 1, -1, -1):
			curr_prod *= arr[i]
			max_prod = max(max_prod, curr_prod)
			if curr_prod == 0:
				curr_prod = 1
		return max_prod


class Solution:

	def maxProduct(self, arr, n):
		maxProd = float('-inf')
		curProd = 1
		for i in arr:
			curProd *= i
			maxProd = max(maxProd, curProd)
			if curProd == 0:
				curProd = 1
		curProd = 1
		for i in range(n - 1, -1, -1):
			curProd *= arr[i]
			maxProd = max(maxProd, curProd)
			if curProd == 0:
				curProd = 1
		return maxProd


class Solution:

	def maxProduct(self, arr, n):
		max_product = arr[0]
		max_prod_till_now = arr[0]
		min_prod_till_now = arr[0]
		for i in range(1, n):
			if arr[i] < 0:
				(max_prod_till_now, min_prod_till_now) = (min_prod_till_now, max_prod_till_now)
			max_prod_till_now = max(arr[i], arr[i] * max_prod_till_now)
			min_prod_till_now = min(arr[i], arr[i] * min_prod_till_now)
			if max_prod_till_now > max_product:
				max_product = max_prod_till_now
		return max_product


class Solution:

	def maxProduct(self, arr, n):
		if n == 0:
			return 0
		(currentMin, currentMax, maxProduct) = (arr[0], arr[0], arr[0])
		for i in range(1, n):
			if arr[i] < 0:
				(currentMax, currentMin) = (currentMin, currentMax)
			currentMax = max(arr[i], currentMax * arr[i])
			currentMin = min(arr[i], currentMin * arr[i])
			maxProduct = max(maxProduct, currentMax)
		return maxProduct


import sys

class Solution:

	def maxProduct(self, arr, n):
		ans = -sys.maxsize - 1
		product = 1
		for i in range(n):
			product *= arr[i]
			ans = max(ans, product)
			if arr[i] == 0:
				product = 1
		product = 1
		for i in range(n - 1, -1, -1):
			product *= arr[i]
			ans = max(ans, product)
			if arr[i] == 0:
				product = 1
		return ans