如何解決leetcode中乘積最大子序列的問題

發布時間：2022-01-17 13:35:52 來源：億速云閱讀：136 作者：小新欄目：大數據

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

題目鏈接

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

題目描述

給定一個整數數組 nums ，找出一個序列中乘積最大的連續子序列（該序列至少包含一個數）。

示例 1:

輸入: [2,3,-2,4]輸出: 6解釋: 子數組 [2,3] 有最大乘積 6。

示例 2:

輸入: [-2,0,-1]輸出: 0解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組。

解題方案

思路

標簽：動態規劃
遍歷數組時計算當前最大值，不斷更新
令imax為當前最大值，則當前最大值為imax = max(imax * nums[i], nums[i])
由于存在負數，那么會導致最大的變最小的，最小的變最大的。因此還需要維護當前最小值imin，imin = min(imin * nums[i], nums[i])
當負數出現時則imax與imin進行交換再進行下一步計算
時間復雜度：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;    }}