乘積最大子序列

給定一個(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ù)組。

?

?

解題思路：乘法與加法最大差別在于，當(dāng)前元素的符號(hào)具有全局性的作用。

如果當(dāng)前元素為負(fù)，那么連乘到上個(gè)元素的最大乘積，再乘以當(dāng)前元素，就變成負(fù)數(shù)，甚至可能成為最小乘積。

同樣，連乘到上個(gè)元素的最小乘積如為負(fù)，再乘以當(dāng)前元素，就變成正數(shù)，甚至可能成為最大乘積。

? ?

因此使用動(dòng)態(tài)規(guī)劃的方法：

記maxLast/minLast為連乘到上個(gè)元素的最大/小乘積

記maxCur/minCur為連乘到當(dāng)前元素的最大/小乘積

記maxAll為全局最大乘積

?

?

1 class Solution{ 2 public: 3 int maxProduct(vector<int>& nums){ 4 if (nums.empty()){ 5 return 0; 6 } 7 if (nums.size() == 1){ 8 return nums[0]; 9 } 10 int maxAll = nums[0];//global maximum 11 int maxLast = nums[0];//maximum including last element 12 int maxCur;//maximum including current element 13 int minLast = nums[0];//minumum including current element 14 int minCur;//minimum including last element 15 for (int i = 1; i<nums.size(); i++){ 16 maxCur = max(nums[i], max(maxLast*nums[i], minLast*nums[i])); 17 minCur = min(nums[i], min(maxLast*nums[i], minLast*nums[i])); 18 maxLast = maxCur; 19 minLast = minCur; 20 maxAll = max(maxAll, maxCur); 21 } 22 return maxAll; 23 } 24 };

?

轉(zhuǎn)載于:https://www.cnblogs.com/kexinxin/p/10196010.html

總結(jié)

以上是生活随笔為你收集整理的Leetcode 152.乘机最大子序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。