DAY 20 試題

問題描述

給定一個整數陣列 nums，找出其中一個子陣列，使得該子陣列的乘積最大，並返回該乘積。子陣列指的是陣列中連續的元素。

例如：

• 輸入：nums = [2,3,-2,4] 輸出：6 解釋：子陣列 [2,3] 的乘積最大，結果為 6。

• 輸入：nums = [-2,0,-1] 輸出：0 解釋：最大乘積為 0，因為子陣列中無法有比 0 更大的乘積。

解題思路

這是一道動態規劃問題，我們需要考慮每個位置上可能的最大值和最小值，因為負數乘以負數會變成正數，這有可能讓結果變得更大。因此，我們需要追蹤每一步的最大值和最小值。
具體步驟如下：

1. 初始化：創建兩個變量 max_product 和 min_product，分別用來保存到目前位置的最大和最小乘積。同時用一個變量 result 來記錄最終結果，初始值設為陣列的第一個元素。
2. 迭代陣列：從第二個元素開始，依次更新當前的 max_product 和 min_product。當遇到負數時，max_product 和 min_product 需要交換，因為負數會使最大的變成最小，最小的變成最大。
3. 更新結果：每次更新完 max_product 後，將它與 result 比較，確保 result 保持最大值。
4. 返回結果：最終返回 result，即為最大乘積子陣列的乘積。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 0;

        int max_product = nums[0], min_product = nums[0], result = nums[0];

        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < 0) {
                swap(max_product, min_product);
            }

            max_product = max(nums[i], max_product * nums[i]);
            min_product = min(nums[i], min_product * nums[i]);

            result = max(result, max_product);
        }

        return result;
    }
};

解法重點與分析

1. 動態規劃策略：由於陣列中可能包含負數，我們同時追蹤最大和最小乘積，確保在負數情況下能正確計算出最大乘積。
2. 交換最大最小乘積：當當前元素為負數時，最大和最小乘積需要交換，因為負數會將正數變成負數，反之亦然。
3. 時間複雜度：O(n)，其中 n 是陣列的長度。我們只需遍歷一次陣列。
4. 空間複雜度：O(1)，只使用了常數的額外空間來儲存中間結果。

總結

這道題的核心在於對負數的處理，我們需要追蹤每一步的最大和最小乘積。透過動態規劃的方法，我們能夠高效地解決這類問題。總體時間複雜度為 O(n)，對於大規模數據來說表現良好。

以上是第二十天的自學內容分享，謝謝大家。