問題描述

給定一個整數數組 nums，請找出數組中乘積最大的連續子數組（該子數組中至少包含一個數字），并返回該子數組對應的乘積。

示例：

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

解題思路

乘積最大子數組問題與和最大子數組問題的關鍵區別在于乘積的符號特性：負數乘以負數會得到正數。這意味著：

1. 不能只維護最大值，還需要維護最小值（因為最小負值可能遇到負數變成最大值）
2. 狀態轉移需要考慮三種情況：當前元素本身、當前元素×前序最大值、當前元素×前序最小值

動態規劃狀態定義

• currentMax：以當前元素結尾的連續子數組的最大乘積
• currentMin：以當前元素結尾的連續子數組的最小乘積
• maxProduct：全局最大乘積（最終結果）

狀態轉移方程

對于每個元素 nums[i]：

temp = currentMax  // 保存前一個位置的最大值
currentMax = max(nums[i], temp * nums[i], currentMin * nums[i])
currentMin = min(nums[i], temp * nums[i], currentMin * nums[i])
maxProduct = max(maxProduct, currentMax)

完整代碼實現

class Solution {public int maxProduct(int[] nums) {