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

示例 1:

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

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

思路：

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

提交的代碼：

class Solution {
? ? public int maxProduct(int[] nums) {
? ? ? ? int max=1,min=1,t,result = -2147483647>>2;
?? ??? ? for(int i=0;i<nums.length;i++)
?? ??? ? {
?? ??? ??? ? if(nums[i]<0)
?? ??? ??? ? {
?? ??? ??? ??? ? t = max;
?? ??? ??? ??? ? max = min;
?? ??? ??? ??? ? min = t;
?? ??? ??? ? }
?? ??? ??? ? max = Math.max(nums[i], nums[i]*max);
?? ??? ??? ? min = Math.min(nums[i], nums[i]*min);
?? ??? ??? ? result = Math.max(max, result);
?? ??? ? }
?? ? ? ? ? return result;?
? ? }
}

完整的代碼：

public class Solution152 {
?? ? public static int maxProduct(int[] nums) {
?? ??? ? int max=1,min=1,t,result = -2147483647>>2;
?? ??? ? for(int i=0;i<nums.length;i++)
?? ??? ? {
?? ??? ??? ? if(nums[i]<0)
?? ??? ??? ? {
?? ??? ??? ??? ? t = max;
?? ??? ??? ??? ? max = min;
?? ??? ??? ??? ? min = t;
?? ??? ??? ? }
?? ??? ??? ? max = Math.max(nums[i], nums[i]*max);
?? ??? ??? ? min = Math.min(nums[i], nums[i]*min);
?? ??? ??? ? result = Math.max(max, result);
?? ??? ? }
?? ? ? ? ? return result;?
?? ? ? ?}
?? ? public static void main(String[] args)
?? ? {
?? ??? ? int nums[] = {-2,0,-1};
?? ??? ? System.out.println(maxProduct(nums));
?? ? }
}
?

總結

以上是生活随笔為你收集整理的Leetcode--152. 乘积最大子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。