卖萌的弱渣

I am stupid, I am hungry.

Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example

Given the array [2,3,-2,4], The contiguous subarray [2,3] has the largest product = 6.

Solution

  • 用数组pos[i]维护原始数组前i个数的子数组乘积中正数的最大值
  • 用数组neg[i]维护原始数组前i个数的子数组乘积中负数的最小值
(Maximum-Product-Subarray.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        pos = []  # positive result array
        neg = []  # negative result array

        pos.append(nums[0])
        neg.append(nums[0])
        for i in range(1,len(nums)):
            pos.append(max(pos[i-1]*nums[i], neg[i-1]*nums[i], nums[i]))
            neg.append(min(pos[i-1]*nums[i], neg[i-1]*nums[i], nums[i]))
        # find the largest in pos array
        ret = pos[0]
        for i in pos:
            if ret < i:
                ret = i
        return ret