152. Maximum Product Subarray

題目網址：https://leetcode.cn/problems/maximum-product-subarray/

題意：給一整數 array nums, 找出乘積最大的非空連續 subarray, 並返回該乘積。

Solution：

想法：定義乘積為區間 [0, i] 中的最大 or 最小乘積。為何乘積必須同時記錄 curMax 和 curMin？因為 array 中可能會有負數, 且負負得正。當 nums[i] 為負數時, 之前紀錄的 curMax 乘它之後變最小值, 也有可能之前紀錄的 curMin 乘它之後變比之前的 curMax 還大。所以當 nums[i] 為負數時, 要將 curMax 和 curMin 做 swap, 這樣才不會出錯

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int curMax = 1, curMin = 1, res = nums[0];

        for (const auto& num : nums) {
            if (num < 0) {
                swap(curMax, curMin);
            }
            curMax = max(num * curMax, num);
            curMin = min(num * curMin, num);
            res = max(res, curMax);
        }
        return res;
    }
};

• time：$O(n)$ ➔ for loop
• space：$O(1)$ ➔ 只需常數空間