題目
#

leetcode 152 - Maximum Product Subarray (題目說明請點連結)

題目簡述
#

給一個整數陣列 nums，找出一個連續子陣列，使得該子陣列中所有數字的乘積最大。
注意：陣列中的數字可以是負數，且子陣列必須包含至少一個數字。

範例
#

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: 子陣列 [2,3] 的乘積為 6，這是最大的乘積。

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: 結果不能為 2，因為 [-2,-1] 不是連續子陣列。

Example 3:

Input: nums = [-2,3,-4]
Output: 24
Explanation: 子陣列 [3,-4] 的乘積為 -12，但整個陣列 [-2,3,-4] 的乘積為 24，這是最大的乘積。

解題思路
#

這題要求我們找到陣列中乘積最大的連續子陣列。由於陣列中可能包含負數，我們需要同時維護最大值和最小值，因為負數乘以負數會變成正數，可能產生更大的乘積。

解法
#

維護三個變數：max（全局最大值）、maxNum（當前最大值）、minNum（當前最小值）
遍歷陣列中的每個數字
如果遇到負數，交換 maxNum 和 minNum
更新 maxNum 和 minNum，考慮當前數字和之前的乘積
更新全局最大值 max

步驟
#

初始化：
- 設定 max = nums[0]（全局最大值）
- 設定 maxNum = nums[0]（當前最大值）
- 設定 minNum = nums[0]（當前最小值）
遍歷陣列：
- 對於每個數字，檢查是否為負數
- 如果是負數，交換 maxNum 和 minNum
更新乘積：
- 更新 maxNum = max(num, maxNum * num)
- 更新 minNum = min(num, minNum * num)
更新全局最大值：
- 比較當前 maxNum 和全局最大值 max

例子說明
#

nums = [2,3,-2,4]

步驟	當前數字	是否為負數	maxNum	minNum	max	說明
初始化	2	否	2	2	2	初始化所有變數
第 1 步	3	否	6	3	6	3 是正數，直接相乘
第 2 步	-2	是	3	-12	6	遇到負數，交換 maxNum 和 minNum
第 3 步	4	否	12	-48	12	4 是正數，繼續相乘

最終結果： 12

乘積計算過程說明：

步驟 1：maxNum = max(3, 2*3) = 6，minNum = min(3, 2*3) = 3
步驟 2：遇到負數 -2，交換 maxNum 和 minNum，然後 maxNum = max(-2, 3*(-2)) = 3，minNum = min(-2, 6*(-2)) = -12
步驟 3：maxNum = max(4, 3*4) = 12，minNum = min(4, -12*4) = -48

完整程式碼
#

java

class Solution {
    public int maxProduct(int[] nums) {
        // 邊界條件：如果陣列為空或長度為 0，返回 0
        if(nums == null || nums.length == 0) {
            return 0;
        }

        // 初始化變數
        int max = nums[0];        // 全局最大值
        int maxNum = nums[0];     // 當前最大值
        int minNum = nums[0];     // 當前最小值

        // 遍歷陣列中的每個數字
        for(int i = 1; i < nums.length; i++){
            int num = nums[i];

            // 如果遇到負數，交換最大值和最小值
            // 因為負數乘以負數會變成正數，可能產生更大的乘積
            if(num < 0){
                int temp = maxNum;
                maxNum = minNum;
                minNum = temp;
            }

            // 更新最大值和最小值
            // 考慮當前數字和之前的乘積
            maxNum = Math.max(num, maxNum * num);
            minNum = Math.min(num, minNum * num);

            // 更新全局最大值
            max = Math.max(max, maxNum);
        }

        return max;
    }
}