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.
My code:
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return 0
dp1 = [x for x in nums]
dp2 = [x for x in nums]
lengthtemp = len(dp1)
for i in range(1,lengthtemp):
dp1[i] = max(dp1[i],dp1[i]*dp1[i-1],dp1[i]*dp2[i-1])
dp2[i] = min(dp2[i],dp2[i]*dp2[i-1],dp2[i]*dp1[i-1])
#print(dp1)
#print(dp2)
return max(dp1)
Solution: https://leetcode.com/problems/maximum-product-subarray/