題意
- 給定一個(gè)整數(shù)數(shù)組 nums 腹纳，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）张症，返回其最大和能庆。
- 給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大乘積的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）颁湖，返回其最大乘積。
注意點(diǎn)
如何以的復(fù)雜度求解它們例隆？
解答
兩個(gè)問題的題干相似甥捺，且都是動(dòng)態(tài)規(guī)劃問題，但具體過程很不一樣镀层。
Maximum Subarray
設(shè)以元素nums[x]為開頭的連續(xù)子數(shù)組的最大和镰禾；只要選出了最佳的
使得
最大皿曲，問題也就解決了。
吴侦，如果等式右邊第二項(xiàng)大于或等于零屋休，則y比x更優(yōu)。
實(shí)現(xiàn)細(xì)節(jié)：
?設(shè)置變量start = 0备韧，它代表我們最初選定的開頭劫樟；temp = nums[0]；index從1遍歷到 len(nums)-1织堂，這是尋找最優(yōu)開頭的過程叠艳；temp代表，如果 temp 小于零易阳，說明index作為開頭比start更優(yōu)秀附较，應(yīng)將 start 改為 index，temp置為nums[index]潦俺，否則說明 index 不如 start：temp加上nums[index]拒课，跳過index，尋找下一個(gè)潛在的更優(yōu)的開頭事示。當(dāng)然別忘了保存循環(huán)中最大的 temp 值早像，這就是連續(xù)子序列的最大和。
Maximum Product Subarray
?假設(shè)有這樣一個(gè)函數(shù) fun(start)很魂，返回2個(gè)值：以start為開頭的連續(xù)子數(shù)組的最大積(必須大于零扎酷，不存在則設(shè)為None)和最小積(必須小于零，不存在則設(shè)置為None)遏匆。
?如果我們已經(jīng)有了 fun(x+1) 的返回值法挨，那求解fun(x)豈不是很容易？按照nums[x] 的正負(fù)情況分 3 類討論即可幅聘，須注意的是如果nums[x]為0凡纳，則fun(x)返回[1,None]。
?找到 t 使 fun(t) 的第一個(gè)返回值最大帝蒿，那個(gè)值即為所求荐糜。
Python代碼
1
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = nums[0]
idx = 1
#start = None
te = nums[0]
while idx < len(nums):
if te < 0:
te = 0
te += nums[idx]
res = max(res, te)
idx += 1
return res
2
class Solution:
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
temp1 = 1
temp2 = None
res = nums[-1]
for idx in range(len(nums)-1,-1,-1):
if nums[idx] != 0:
if temp1 and temp2:
t1 = max(temp1*nums[idx], temp2*nums[idx])
t2 = min(temp1*nums[idx], temp2*nums[idx])
temp1,temp2 = t1,t2
elif temp1 and not temp2:
if nums[idx] > 0:
temp1 *= nums[idx]
else:
temp2 = temp1*nums[idx]
temp1 = None
elif not temp1 and temp2:
if nums[idx] > 0:
temp2 *= nums[idx]
temp1 = nums[idx]
else:
temp1 = temp2*nums[idx]
temp2 = nums[idx]
else:
temp1 = 1
temp2 = None
res = max(0,res)
continue
if temp1:
res = max(res, temp1)
return res
