題目

　　給定一個double類型的數(shù)組arr，其中的元素可正、可負(fù)、可0，返回子數(shù)組累乘的最大乘積。例如，arr = [-2.5, 4, 0, 3, 0.5, 8, -1]，子數(shù)組[3, 0.5, 8]累乘可以獲得最大的乘積12，所以返回12.

基本思路

　　本題可以做到時間復(fù)雜度O(N)、空間復(fù)雜度O(1).

　　大致思路是，遍歷一遍數(shù)組，求出以每一個元素結(jié)尾的子數(shù)組的最大累乘積。如何快速的求出以 i 位置結(jié)尾的子數(shù)組的最大累積呢？假設(shè)以arr[i-1]結(jié)尾的最小乘積是min，最大乘積是max。那么，以arr[i]結(jié)尾的最大累乘積只可能來自以下三種情況：

可能是max * arr[i]

可能是min * arr[i]，因為數(shù)組中可能包含負(fù)數(shù)，負(fù)負(fù)得正

可能是arr[i]，因為以arr[i-1]結(jié)尾的最大乘積可能小于1

這三種可能的值中最大的那個就作為以 i 位置結(jié)尾的最大累乘積，最小的作為最小累乘積，繼續(xù)遍歷下一個位置
?

def maxProduct(L):if L == None or len(L) == 0:return 0max_,min_,res = L[0],L[0],L[0]maxEnd,minEnd = 0,0for i in range(1,len(L)):maxEnd = max_ * L[i]minEnd = min_ * L[i]max_ = max(max(maxEnd,max_),L[i])min_ = min(min(minEnd,min_),L[i])res = max(max_,res)return res

?

總結(jié)

以上是生活随笔為你收集整理的数组中子数组的最大累乘积的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。