Maximum Product Subarray

题目

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

For example, given the array[2,3,-2,4],
the contiguous subarray[2,3]has the largest product =6.

思路分析

这道题刚开始没有什么思路，仔细读题及分析题意可以基本确定用动态规划来解决。要用动态规划来解决就要先弄清楚动态规划的四个要素，最关键的就是函数的定义，以及当前值都跟之前的那些值相关

对于本题而言，假设已经直到了从0到i-1的每一个subarray的product的最大值，那么包含第i个num的subarray的最大product值跟那些因素有关呢？首先可能是包含第i-1的subarray的max product * 当前num，可能当前num就是最大值，由于nums中的每一个元素可能是负数，那么就还存在一种可能性就是包含第i-1的subarray的min product * 当前num

根据以上的分析，我们基本可以确定动态规划的方程了，那么如何定义呢？在这里我们需要定义两个数组

• maxList[i]：maximum product that can be achieved ending with i
• minList[i]：minimum product that can be achieved ending with i

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        minList = [0] * len(nums)
        maxList = [0] * len(nums)
        minList[0] = nums[0]
        maxList[0] = nums[0]
        result = nums[0]
        for i in xrange(1, len(nums)):
            maxList[i] = max(max(maxList[i-1] * nums[i], minList[i-1] * nums[i]), nums[i])
            minList[i] = min(min(minList[i-1] * nums[i], maxList[i-1] * nums[i]), nums[i])
            result = max(result, maxList[i])
        return result