溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

如何解決leetcode中乘積最大子序列的問(wèn)題

發(fā)布時(shí)間：2022-01-17 13:35:52 來(lái)源：億速云 閱讀：130 作者：小新 欄目：大數(shù)據(jù)

這篇文章主要介紹了如何解決leetcode中乘積最大子序列的問(wèn)題，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

 

題目鏈接

https://leetcode-cn.com/problems/maximum-product-subarray/

 

題目描述

給定一個(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)?nbsp;[-2,-1] 不是子數(shù)組。
 
 

解題方案

 

思路

  • 標(biāo)簽：動(dòng)態(tài)規(guī)劃

  • 遍歷數(shù)組時(shí)計(jì)算當(dāng)前最大值，不斷更新

  • 令imax為當(dāng)前最大值，則當(dāng)前最大值為imax = max(imax * nums[i], nums[i])

  • 由于存在負(fù)數(shù)，那么會(huì)導(dǎo)致最大的變最小的，最小的變最大的。因此還需要維護(hù)當(dāng)前最小值imin，imin = min(imin * nums[i], nums[i])

  • 當(dāng)負(fù)數(shù)出現(xiàn)時(shí)則imax與imin進(jìn)行交換再進(jìn)行下一步計(jì)算

  • 時(shí)間復(fù)雜度：O(n)

 

代碼

class Solution {    public int maxProduct(int[] nums) {        int max = Integer.MIN_VALUE, imax = 1, imin = 1;        for(int i=0; i<nums.length; i++){            if(nums[i] < 0){               int tmp = imax;              imax = imin;              imin = tmp;            }            imax = Math.max(imax*nums[i], nums[i]);            imin = Math.min(imin*nums[i], nums[i]);                        max = Math.max(max, imax);        }        return max;    }}
 
 

畫解


如何解決leetcode中乘積最大子序列的問(wèn)題

如何解決leetcode中乘積最大子序列的問(wèn)題

如何解決leetcode中乘積最大子序列的問(wèn)題如何解決leetcode中乘積最大子序列的問(wèn)題如何解決leetcode中乘積最大子序列的問(wèn)題如何解決leetcode中乘積最大子序列的問(wèn)題

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“如何解決leetcode中乘積最大子序列的問(wèn)題”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手