152. Maximum Product Subarray

Medium

Description

給定一個整數陣列 nums，找出一個乘積最大的連續子陣列（至少包含一個元素），回傳其乘積。

Example:

Input: nums = [2,3,-2,4] Output: 6

Intuition#

負數乘以負數會變正數，所以必須同時追蹤當前的最大值和最小值。

不同於最大子陣列和，乘積的負號會翻轉大小關係
遇到負數時，當前最大值和最小值會互換
每步都要考慮三種可能：nums[i] 本身、curMax * nums[i]、curMin * nums[i]

Approaches#

1: Brute Force (Enumerate All Subarrays)#

概念: 枚舉所有子陣列的起點和終點，計算乘積並取最大值
時間複雜度: O(n^2)
空間複雜度: O(1)

class Solution {
    fun maxProduct(nums: IntArray): Int {
        var result = nums[0]
        for (i in nums.indices) {
            var product = 1
            for (j in i until nums.size) {
                product *= nums[j]
                result = maxOf(result, product)
            }
        }
        return result
    }
}

⭐2: Track Min and Max#

概念: 同時維護以當前元素結尾的最大乘積和最小乘積，遇負數時交換
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun maxProduct(nums: IntArray): Int {
        var result = nums[0]
        var curMax = 1
        var curMin = 1
        for (num in nums) {
            val candidates = longArrayOf(num.toLong() * curMax, num.toLong() * curMin, num.toLong())
            curMax = candidates.max().toInt()
            curMin = candidates.min().toInt()
            result = maxOf(result, curMax)
        }
        return result
    }
}

🔑 Takeaways#

Pattern: 雙狀態 DP — 當正負性會影響結果時，需要同時追蹤最大和最小
關鍵技巧: 乘積問題中負數的處理：負 * 負 = 正，所以最小值可能在下一步變成最大值