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