資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目乘積最大子序列給定一個(gè)整數(shù)數(shù)組，找出一個(gè)序列中乘積最大的連續(xù)子序列該序列至少包含一個(gè)數(shù)。示例輸入輸出解釋結(jié)果不能為因?yàn)椴皇亲訑?shù)組。當(dāng)大于時(shí)如果，，如果，，時(shí)間復(fù)雜度和空間復(fù)雜度均為，其中是數(shù)組中的元素個(gè)數(shù)。動(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ù)組。
class Solution:
def maxProduct(self, nums: List[int]) -> int:
max = nums[0]
for i in range(len(nums)):
prod = 1
for j in range(i, len(nums)):
prod *= nums[j]
if prod > max:
max = prod
return max
執(zhí)行代碼 OK通過(guò)
我們?cè)僮孕袦y(cè)試一遍
先將測(cè)試用例改為[-2], OK也沒(méi)問(wèn)題
如果測(cè)試用例非常長(zhǎng),那么該方法肯定不可取,因?yàn)槠鋾r(shí)間復(fù)雜度為O(n^2)
class Solution:
def maxProduct(self, nums: list) -> int:
B = nums[::-1]
for i in range(1, len(nums)):
nums[i] *= nums[i - 1] or 1
B[i] *= B[i - 1] or 1
return max(max(nums), max(B))
這個(gè)方法我有點(diǎn)搞不明白
按理來(lái)說(shuō) 設(shè)nums中元素個(gè)數(shù)為x,則理論上應(yīng)該有
$$ sum_{i=1}^x x = frac{1}{2} x^2 + frac{1}{2} x $$
個(gè)非空子序列,而上面這個(gè)方法中nums和B僅列出了x+x=2x個(gè)非空子序列
動(dòng)態(tài)規(guī)劃狀態(tài)定義：
f(x) -------- nums數(shù)組中[0, x]范圍內(nèi)的最大連續(xù)子序列的乘積，且該連續(xù)子序列以nums[x]結(jié)尾
g(x)?-------- nums數(shù)組中[0, x]范圍內(nèi)的最小連續(xù)子序列的乘積，且該連續(xù)子序列以nums[x]結(jié)尾
狀態(tài)轉(zhuǎn)移：
（1）當(dāng)x等于0時(shí)，顯然此時(shí)[0, x]范圍內(nèi)只有一個(gè)元素，f(0)和g(0)均等于這個(gè)唯一的元素。
（2）當(dāng)x大于0時(shí)
a：如果nums[x] >= 0，f(x) = max(f(x - 1) nums[x], nums[x])，g(x) = min(g(x - 1) nums[x], nums[x])
b：如果nums[x] < 0，f(x) = max(g(x - 1) nums[x], nums[x])，g(x) = min(f(x - 1) nums[x], nums[x])
時(shí)間復(fù)雜度和空間復(fù)雜度均為O(n)，其中n是nums數(shù)組中的元素個(gè)數(shù)。
class Solution:
def maxProduct(self, nums: List[int]) -> int:
maxpd = []
minpd = []
for i in range(len(nums)):
if i == 0:
maxpd.append(nums[0])
minpd.append(nums[0])
else:
if nums[i] >= 0:
maxpd.append(max(maxpd[i-1]*nums[i], nums[i]))
minpd.append(min(minpd[i-1]*nums[i], nums[i]))
else:
maxpd.append(max(minpd[i-1]*nums[i], nums[i]))
minpd.append(min(maxpd[i-1]*nums[i], nums[i]))
return max(maxpd)
動(dòng)態(tài)規(guī)劃法參考自https://blog.csdn.net/qq_4123...
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/44090.html
摘要：題目要求從一個(gè)整數(shù)數(shù)組中找到一個(gè)子數(shù)組，該子數(shù)組中的所有元素的乘積最大。比如數(shù)組的最大乘積子數(shù)組為思路與代碼這題目考察了動(dòng)態(tài)編程的思想。至于為什么還要比較，是因?yàn)槿绻且粋€(gè)負(fù)數(shù)的，那么之前的最小乘積在這里可能就成為了最大的乘積了。 題目要求 Find the contiguous subarray within an array (containing at least one num...
摘要：認(rèn)真做題的分割線(xiàn)第一題乘積最大子序列難度中等給定一個(gè)整數(shù)數(shù)組，找出一個(gè)序列中乘積最大的連續(xù)子序列該序列至少包含一個(gè)數(shù)。 寫(xiě)在前面的話(huà) 慢慢轉(zhuǎn)變思路，不再死磕不會(huì)做的題，思路可以先借鑒，但是一定要吃透透。上周末看完看完了《算法圖解》，感覺(jué)對(duì)一些題目的思路有比較大的幫助，但是還是要在實(shí)踐中理解。 認(rèn)真做題的分割線(xiàn) 第一題 152. 乘積最大子序列難度：中等給定一個(gè)整數(shù)數(shù)組nums，找出一個(gè)...
摘要：在線(xiàn)網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線(xiàn)網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：思路動(dòng)態(tài)規(guī)劃，前五個(gè)數(shù)的最大乘積為，后面的第個(gè)數(shù)的最大乘積，由從后往前數(shù)包括本身的第三個(gè)數(shù)乘以得到。何睿何睿前個(gè)數(shù)的最大乘積動(dòng)態(tài)規(guī)劃第個(gè)數(shù)的最大乘積為往前數(shù)第三個(gè)數(shù)思路與上面的思路一致，優(yōu)化了空間源代碼文件在這里。 Description Given a positive integer n, break it into the sum of at least two positive...
摘要：本質(zhì)找出最長(zhǎng)的遞增子序列的長(zhǎng)度，可以是不連續(xù)的。應(yīng)用判斷滿(mǎn)足一定條件的子序列的最大長(zhǎng)度，用動(dòng)態(tài)數(shù)組加以處理。二分法確定滿(mǎn)足條件的位置。類(lèi)似二分法查找元素，查找某種情況的子序列。 本質(zhì)： 找出最長(zhǎng)的遞增子序列的長(zhǎng)度，可以是不連續(xù)的。 用一個(gè)數(shù)組存儲(chǔ) 遞增子序列，遍歷原始數(shù)組，每增加一個(gè)數(shù)，往里添加到對(duì)應(yīng)的順序，記錄他的位置，即為此數(shù)組的長(zhǎng)度。 成立的理由：每一個(gè)數(shù)添加以后，都有對(duì)...
閱讀 3499·2023-04-25 21:43
閱讀 3109·2019-08-29 17:04
閱讀 814·2019-08-29 16:32
閱讀 1548·2019-08-29 15:16
閱讀 2161·2019-08-29 14:09
閱讀 2754·2019-08-29 13:07
閱讀 1638·2019-08-26 13:32
閱讀 1331·2019-08-26 12:00
