image.png
152. 乘積最大子序列
- 乘積最大子序列
給定一個整數(shù)數(shù)組 nums ，找出一個序列中乘積最大的連續(xù)子序列（該序列至少包含一個數(shù)）张吉。
示例 1:
輸入: [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [2,3] 有最大乘積 6。
示例 2:
輸入: [-2,0,-1]
輸出: 0
解釋: 結(jié)果不能為 2, 因為 [-2,-1] 不是子數(shù)組。
Python3 實現(xiàn)
暴力求解
#@author:leacoder
#@des: 暴力求解 乘積最大子序列
# leetcode 超時
class Solution:
def maxProduct(self, nums: List[int]) -> int:
maxnum = float("-inf")
for i in range(0,len(nums)):
tmp = nums[i]
for j in range(i+1,len(nums)):
tmp *= nums[j]
maxnum = max(maxnum,tmp)
maxnum = max(maxnum,nums[i])
return maxnum
動態(tài)規(guī)劃 1
#@author:leacoder
#@des: 動態(tài)規(guī)劃 乘積最大子序列
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if nums is None : return 0
imax = [0,0]
imin = [0,0]
imax[0], imin[0],res= nums[0],nums[0],nums[0]
for i in range(1,len(nums)):
x,y=i%2,(i-1)%2 # x 表示當(dāng)前最大或最小下標(biāo) y 表示前面最大或最小下標(biāo)
imax[x] = max( imax[y] * nums[i], imin[y] * nums[i], nums[i] )
# nums[i]可能為負(fù)數(shù)牡拇，若為負(fù)數(shù) 前面最小 * nums[i]變?yōu)樽畲罂谒模懊孀畲?* nums[i]變?yōu)樽钚? imin[x] = min( imax[y] * nums[i], imin[y] * nums[i], nums[i] )
res = max(res,imax[x])
return res
動態(tài)規(guī)劃 2
#@author:leacoder
#@des: 動態(tài)規(guī)劃 乘積最大子序列
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if nums is None : return 0
res , curMax, curMin = nums[0],nums[0],nums[0]
for i in range(1,len(nums)):
num = nums[i]
curMax, curMin = curMax * num, curMin * num
# 由于 num可能為負(fù)數(shù) 上面結(jié)果可能剛好反了, curMax * 負(fù)數(shù)變?yōu)?curMin 顧需要下面語句處理
curMax,curMin = max(curMax,curMin,num),min(curMax,curMin,num)
res = max(curMax,res)
return res
動態(tài)規(guī)劃 3
#@author:leacoder
#@des: 動態(tài)規(guī)劃 乘積最大子序列
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if nums is None : return 0
res , curMax, curMin = nums[0],nums[0],nums[0]
for i in range(1,len(nums)):
num = nums[i]
if num < 0 :
curMax, curMin = curMin, curMax # 由于 num為負(fù)數(shù) 導(dǎo)致最大的變最小的孵运，最小的變最大的,因此交換兩個的值
curMax = max(curMax*num,num)
curMin = min(curMin*num,num)
res = max(curMax,res)
return res
GitHub鏈接：
https://github.com/lichangke/LeetCode
知乎個人首頁：
https://www.zhihu.com/people/lichangke/
簡書個人首頁：
http://www.reibang.com/u/3e95c7555dc7
個人Blog:
https://lichangke.github.io/
歡迎大家來一起交流學(xué)習(xí)
