題目鏈接
難度： 中等 ??????類型：動(dòng)態(tài)規(guī)劃
給定一個(gè)整數(shù)數(shù)組 nums 遂蛀，找出一個(gè)序列中乘積最大的連續(xù)子序列（該序列至少包含一個(gè)數(shù)）品抽。
示例1
輸入: [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [2,3] 有最大乘積 6哩陕。
示例2
輸入: [-2,0,-1]
輸出: 0
解釋: 結(jié)果不能為 2, 因?yàn)?[-2,-1] 不是子數(shù)組。
解題思路
乘積子數(shù)組中可能有正數(shù)褐荷、負(fù)數(shù)计济，也可能有 0。因?yàn)橛胸?fù)數(shù)的存在各吨，所以可以考慮同時(shí)找出最大乘積和最小乘積枝笨。于是，問題簡(jiǎn)化成這樣：在數(shù)組中找到一個(gè)子數(shù)組揭蜒，使得它的乘積最大横浑，同時(shí)再找到另一個(gè)子數(shù)組，使得它的乘積最刑敫（含有負(fù)數(shù)的情況）徙融。也就是說，不但記錄最大乘積瑰谜，也記錄最小乘積欺冀。
假設(shè)數(shù)組為 a[]，直接利用動(dòng)態(tài)規(guī)劃來求解似舵〗呕考慮到負(fù)數(shù)的情況，用maxend來表示以 a[i]結(jié)尾的最大連續(xù)子數(shù)組的乘積值砚哗，用 minend 表示以 a[i]結(jié)尾的最小連續(xù)子數(shù)組的乘積值龙助，那么狀態(tài)轉(zhuǎn)移方程為：
maxend = max(max(maxend * a[i], minend * a[i]), a[i]);
minend = min(min(maxend * a[i], minend * a[i]), a[i]);
代碼實(shí)現(xiàn)
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
dp_max = [nums[0]]*n
dp_min = [nums[0]]*n
res = nums[0]
for i in range(1,n):
dp_max[i] = max(dp_max[i-1]*nums[i], nums[i], dp_min[i-1]*nums[i])
dp_min[i] = min(dp_max[i-1]*nums[i], nums[i], dp_min[i-1]*nums[i])
res = max(res,dp_max[i])
return res
