0152._maximum_product_subarray.md

152. Maximum Product Subarray

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/maximum-product-subarray/description/

内容描述

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.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

粗一看， 一股浓烈的DP气息飘来，想要套用53题的思路和方程。但是这个跟sum是不一样的，因为乘积可以正负正负的跳，这样的动归方程肯定是不对的

dp[i] = max(dp[i-1] * a[i],a[i])

举个例子 ： [-2,3,-4]

我猜想可不可以记录正的和负的，记录两个dp数组，因为刚才最小的可能突然就变成最大的了，比如刚才是-7，最小，现在(-7)*(-3) = 21可能就最大了

最大值可能来源于最小值 -> 哲学般的句子

beats 98.99%

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxdp = [nums[0]] * len(nums)
        mindp = [nums[0]] * len(nums)

        for i in range(1, len(nums)):
        	maxdp[i] = max(mindp[i-1]*nums[i], maxdp[i-1]*nums[i], nums[i])
        	mindp[i] = min(maxdp[i-1]*nums[i], mindp[i-1]*nums[i], nums[i])

        return max(maxdp)

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

寒神的思路

• Calculate prefix product in A.
• Calculate suffix product in A.
• Return the max.

beats 99.93%

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        reverse = nums[::-1]
        for i in range(1, len(nums)):
            nums[i] *= nums[i-1] or 1
            reverse[i] *= reverse[i-1] or 1
        return max(nums + reverse)