讲解你最可能遇见的坑

一看本题目知识点是动态规划
dp[i] = dp[i-1]的一系列操作
但是发现未果,因为是连续的子树组,所以最小值也可能摇身一变把歌唱,成为最大值.所以三十年河东....
所以可以定义一个imax imin,来分别遍历最大值和最小值.

dp公式:

imax = max(arr[i]*imax,arr[i]*imin,arr[i])
imin = min(arr[i]*imax,arr[i]*imin,arr[i])

但是最大的坑!这时候第一次计算的时候imax值会更改,所以imin计算的imax,是应该被计算的imax的子imax.

所以可以改称

imax,imin = max(arr[i]*imax,arr[i]*imin,arr[i]),min(arr[i]*imax,arr[i]*imin,arr[i])

当然,我们也可以定义一个,中间变量temp

完整代码如下

class Solution:
    def maxProduct(self , arr ):
        if arr == []: return 0.0
        imax ,imin ,res = arr[0], arr[0], arr[0]
        for i in range(1,len(arr)):
            imax,imin = max(arr[i]*imax,arr[i]*imin,arr[i]),min(arr[i]*imax,arr[i]*imin,arr[i])
            res = max(res,imax)
        return res