152. Maximum Product Subarray

问题描述

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
Example 2:
Input: [-2,0,-1]
Output: 0

思路：

loop一遍，用三个值mini、maxi(某一区间)，和ans（最终return的值）

1. 对于每个数字，如果小于0，交换mini和maxi的值，因为乘负数大的变小，小的变大
2. 其次，mini = min(mini*i, i), maxi = max(maxi*i, i), 看这个区间还能不能乘出新的maxi或mini值
3. ans每次确认是否需要更新

    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return
        mini = maxi = ans = nums[0]

        for i in nums[1:]:
            if i < 0:
                tmp = mini
                mini = maxi
                maxi = tmp
            mini = min(i * mini, i)
            maxi = max(i * maxi, i)
            ans = max(ans, maxi)
        return ans