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: 6Explanation: [2,3] has the largest product 6.

Example 2:

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

 

08/01/2018 update: 在code里面可以用

dp_max[i%2] = max(ma, mi, num)dp_min[i%2] = min(mi, mi, num) 去代替之前的6行.

这个题目实际上是的follow up, 有点要注意的是如果我们只用 A[i] 是max value which contains nums[i] for sure, 

then A[i] = max(A[i-1] * nums[i], nums[i]), 不够了, 比如说 [2, 3, -2, 4, -1] , 最大值应该为48, 但是我们得到最大值为6, 因为在nums[i] < 0 时, 我们应该将之前的最小值* nums[i] 去得到最大值. 所以有两个dp数组, 一个记录最小值, 一个记录最大值, 每次将最大值和ans比较, 最后返回ans

 

1. Constraints

1) size >=1 

2)element , integer

 

2. Ideas

Dynamic Programming        T: O(n)     S; O(1)   using rolling array

 

3. Code

3.1) S; O(n)

class Solution:    def maxProductSubarry(self, nums):        n = len(nums)        dp_max, dp_min = [0]*n, [0]*n        dp_max[0], dp_min[0], ans = nums[0], nums[0], nums[0]        for i in range(1, n):            if nums[i] > 0:                dp_max[i] = max(dp_max[i-1] * nums[i], nums[i])                dp_min[i] = min(dp_min[i-1] * nums[i], nums[i])            else:                dp_max[i] = max(dp_min[i-1] * nums[i], nums[i])                dp_min[i] = min(dp_max[i-1] * nums[i], nums[i])            ans = max(ans, dp_max[i])        return ans

 

3.2) S; O(1) using rolling array

class Solution:    def maxProductSubarry(self, nums):        n, n0 = len(nums), nums[0]        dp_max, dp_min, ans = [n0] + [0], [n0] +[0], n0        for i in range(1, n):            num, ma, mi = nums[i], dp_max[(i-1) % 2] * nums[i], dp_min[(i-1) % 2] * nums[i]            if num > 0:                dp_max[i%2] = max(ma, num)                dp_min[i%2] = min(mi, num)            else:                dp_max[i%2] = max(mi, num)                dp_min[i%2] = min(ma, num)            ans = max(ans, dp_max[i%2])        return ans

 

 

4. Test cases

 

 [2, 3, -2, 4, -1]