Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product. It is guaranteed that the answer will fit in a 32-bit integer. A subarray is a contiguous subsequence of the array.
Example 1: Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.
- code
class Solution:
def maxProduct(self, nums: List[int]) -> int:
self.res = nums[0]
def cal(nums): # nums doesn't have 0
if not nums: return
l, r = 0, len(nums)-1
cur_res = prod(nums[l:r+1])
if cur_res > 0:
self.res = max(self.res, cur_res)
else: # find the first and last negative num, remove each and cal
while nums[l] > 0: l += 1
while nums[r] > 0: r -= 1
if l + 1 < len(nums): cal(nums[l+1:])
if r > 0: cal(nums[:r])
while nums: # split list with 0
try:
i = nums.index(0)
self.res = max(0, self.res)
cal(nums[:i])
nums = nums[i+1:]
except:
cal(nums)
break
return self.res