152. Maximum Product Subarray

#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#

Brute Force (Enumerate All Subarrays) — O(n^2) / O(1)

概念: 枚舉所有子陣列的起點和終點，計算乘積並取最大值
時間複雜度: 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
    }
}

DP with Min/Max Arrays — O(n) / O(n)

概念: 顯式建立兩個 DP 陣列 dpMax[i] 與 dpMin[i]，分別代表「以 nums[i] 結尾的最大／最小乘積」。狀態轉移：dpMax[i] = max(nums[i], dpMax[i-1]*nums[i], dpMin[i-1]*nums[i])，dpMin[i] 對稱。
時間複雜度: O(n) - 每個位置 O(1) 轉移
空間複雜度: O(n) - 兩條 DP 陣列

class Solution {
    fun maxProduct(nums: IntArray): Int {
        val n = nums.size
        val dpMax = IntArray(n)
        val dpMin = IntArray(n)
        dpMax[0] = nums[0]
        dpMin[0] = nums[0]
        var result = nums[0]
        for (i in 1 until n) {
            val a = nums[i]
            val b = dpMax[i - 1] * nums[i]
            val c = dpMin[i - 1] * nums[i]
            dpMax[i] = maxOf(a, b, c)
            dpMin[i] = minOf(a, b, c)
            result = maxOf(result, dpMax[i])
        }
        return result
    }
}

⭐ 3. Track Min and Max — O(n) / O(1)

概念: 同時維護以當前元素結尾的最大乘積和最小乘積，遇負數時交換
時間複雜度: 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 — 當正負性會影響結果時，需要同時追蹤最大和最小
關鍵技巧: 乘積問題中負數的處理：負 * 負 = 正，所以最小值可能在下一步變成最大值