Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:


Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.


Example 2:


Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def maxProduct(self, nums):

		def prod(nums):
			prod = 1
			for i in nums:
				prod *= i
			return prod

		def listsplit(ls1, index):
			result = []
			st = -1
			for i in index:
				if i == 0:
					st = i
				else:
					result.append(ls1[st + 1:i])
					st = i
			if st < len(ls1) - 1:
				result.append(ls1[st + 1:])
			return result
		if not nums:
			return 0
		if len(nums) == 1:
			return nums[0]
		result = []
		if 0 in nums:
			zeros = [i for i in range(len(nums)) if nums[i] == 0]
			sublist = listsplit(nums, zeros)
			result.append(0)
		else:
			sublist = [nums]
		sublist = [i for i in sublist if i]
		for i in sublist:
			if prod(i) < 0:
				negative = [j for j in range(len(i)) if i[j] < 0]
				(left, right) = (negative[0], negative[-1])
				if len(i) == 1:
					result_t = i[0]
				elif left == 0 or right == len(i) - 1:
					result_t = max(prod(i[left + 1:]), prod(i[:right]))
				else:
					(left_p, right_p) = (prod(i[:left]), prod(i[right + 1:]))
					if left_p <= right_p:
						result_t = prod(i[left + 1:])
					else:
						result_t = prod(i[:right])
			else:
				result_t = prod(i)
			result.append(result_t)
		return max(result)


class Solution:

	def maxProduct(self, nums):
		self._prod_cache = {}
		m_value = None
		if len(nums) == 1:
			return nums[0]
		if len(nums) == 0:
			return 0
		for i in range(len(nums)):
			a_value = self.get_max_prod(nums, i, 1)
			if m_value is None or a_value > m_value:
				m_value = a_value
		return m_value

	def get_max_prod(self, nums, i, acc_p):
		if i < 0:
			return None
		if (i, acc_p) in self._prod_cache:
			return self._prod_cache[i, acc_p]
		val = nums[i]
		if i > 0:
			max_p = max(self.get_max_prod(nums, i - 1, acc_p * val), acc_p * val)
		else:
			max_p = acc_p * val
		self._prod_cache[i, acc_p] = max_p
		return max_p


class Solution:

	def maxProduct(self, nums):
		n = len(nums)
		if n == 0:
			return 0
		if n == 1:
			return nums[0]
		ans = nums[0]
		l = 0
		r = n - 1
		prod = 1
		i = 0
		while i < n:
			if nums[i] == 0:
				zero_idx = i
				return max(self.maxProduct(nums[zero_idx + 1:]), max(0, self.maxProduct(nums[0:zero_idx])))
			else:
				prod = prod * nums[i]
				i = i + 1
		if prod > 0:
			return prod
		prod_right = prod
		max_prod_right = prod
		prod_left = prod
		max_prod_left = prod
		if prod < 0:
			while 0 <= r:
				prod_right = prod_right // nums[r]
				r = r - 1
				if prod_right > max_prod_right:
					if prod_right > 0:
						max_prod_right = prod_right
						break
					else:
						max_prod_right = prod_right
			print(max_prod_left)
			while l < n:
				prod_left = prod_left // nums[l]
				l = l + 1
				if prod_left > max_prod_left:
					if prod_left > 0:
						max_prod_left = prod_left
						break
				else:
					max_prod_left = prod_left
		return max(max_prod_left, max_prod_right)


class Solution:

	def maxProduct(self, nums):
		if not nums:
			return 0
		res = premax = premin = nums[0]
		curmax = curmin = None
		for n in nums[1:]:
			(curmax, curmin) = (max(premax * n, premin * n, n), min(premax * n, premin * n, n))
			(premax, premin) = (curmax, curmin)
			res = max(res, curmax)
		return res


class Solution:

	def maxProduct(self, nums):
		glo_max = nums[0]
		imax = glo_max
		imin = glo_max
		i = 1
		while i < len(nums):
			if nums[i] < 0:
				temp = imax
				imax = imin
				imin = temp
			imax = max(nums[i], nums[i] * imax)
			imin = min(nums[i], nums[i] * imin)
			glo_max = max(glo_max, imax)
			i += 1
		return glo_max


class Solution(object):

	def maxProduct(self, nums):
		if len(nums) == 0:
			return nums
		if len(nums) == 1:
			return nums[0]
		curr_min = curr_max = best_max = nums[0]
		for i in range(1, len(nums)):
			(curr_min, curr_max) = (min(nums[i], nums[i] * curr_min, nums[i] * curr_max), max(nums[i], nums[i] * curr_min, nums[i] * curr_max))
			best_max = max(curr_max, best_max)
		return best_max


class Solution:

	def maxProduct(self, nums):
		dp_max = [0] * len(nums)
		dp_min = [0] * len(nums)
		res = dp_max[0] = dp_min[0] = nums[0]
		for i in range(1, len(nums)):
			dp_max[i] = max(nums[i], dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i])
			dp_min[i] = min(nums[i], dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i])
			res = max(res, dp_max[i])
		return res


class Solution:

	def maxProduct(self, nums):
		max_val = -float('inf')
		product = 1
		for num in nums:
			product *= num
			max_val = max(product, max_val)
			if num == 0:
				product = 1
		product = 1
		for num in nums[::-1]:
			product *= num
			max_val = max(product, max_val)
			if num == 0:
				product = 1
		return max_val


class Solution:

	def maxProduct(self, nums):
		if not nums:
			return 0
		res = loc_min = loc_max = nums[0]
		for i in nums[1:]:
			if i < 0:
				(loc_min, loc_max) = (loc_max, loc_min)
			loc_min = min(i, loc_min * i)
			loc_max = max(i, loc_max * i)
			res = max(loc_min, loc_max, res)
		return res


class Solution:

	def maxProduct(self, nums):
		if len(nums) == 1:
			return nums[0]
		else:
			result = big = small = nums[0]
		for i in nums[1:]:
			(big, small) = (max(i, i * big, i * small), min(i, i * small, i * big))
			result = max(result, big)
		return result


class Solution:

	def maxProduct(self, nums):
		n = len(nums)
		dp = [[nums[0], nums[0]]] * n
		ans = nums[0]
		for i in range(1, n):
			temp = [dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i], nums[i]]
			(dp[i][0], dp[i][1]) = (max(temp), min(temp))
			if dp[i][0] > ans:
				ans = dp[i][0]
		return ans


class Solution:

	def maxProduct(self, nums):
		f = [[nums[0], nums[0]]]
		ans = nums[0]
		for i in range(1, len(nums)):
			f.append([0, 0])
			f[i][0] = min(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i])
			f[i][1] = max(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i])
			ans = max(ans, f[i][1])
		return ans


class Solution:

	def maxProduct(self, nums):
		largestproduct = []
		smallestproduct = []
		n = len(nums)
		largestproduct.append(nums[0])
		smallestproduct.append(nums[0])
		for i in range(n - 1):
			lp = max(max(largestproduct[i] * nums[i + 1], smallestproduct[i] * nums[i + 1]), nums[i + 1])
			sp = min(min(largestproduct[i] * nums[i + 1], smallestproduct[i] * nums[i + 1]), nums[i + 1])
			largestproduct.append(lp)
			smallestproduct.append(sp)
		sol = largestproduct[0]
		for i in range(n):
			sol = max(sol, largestproduct[i])
		return sol


class Solution:

	def maxProduct(self, nums):
		maxPos = nums[0]
		maxNeg = -nums[0]
		p = 1
		result = nums[0]
		while p < len(nums):
			if nums[p] >= 0:
				tmp1 = max(nums[p], nums[p] * maxPos)
				tmp2 = max(-nums[p], nums[p] * maxNeg)
				maxPos = tmp1
				maxNeg = tmp2
			else:
				tmp1 = max(nums[p], -nums[p] * maxNeg)
				tmp2 = max(-nums[p], -nums[p] * maxPos)
				maxPos = tmp1
				maxNeg = tmp2
			print((nums[p], maxPos, maxNeg))
			result = max(result, maxPos)
			p += 1
		return result


class Solution:

	def maxProduct(self, nums):
		maxP = nums[0]
		minP = nums[0]
		p = 1
		result = nums[0]
		while p < len(nums):
			tmp1 = max(nums[p], nums[p] * maxP, nums[p] * minP)
			tmp2 = min(nums[p], nums[p] * maxP, nums[p] * minP)
			maxP = tmp1
			minP = tmp2
			print((nums[p], maxP, minP))
			result = max(result, maxP)
			p += 1
		return result