給定一個整數陣列
nums，找出一個乘積最大的連續子陣列（至少包含一個元素），回傳其乘積。
Example:
Input: nums = [2,3,-2,4] Output: 6
Intuition
TIP
負數乘以負數會變正數，所以必須同時追蹤當前的最大值和最小值。
- 不同於最大子陣列和，乘積的負號會翻轉大小關係
- 遇到負數時，當前最大值和最小值會互換
- 每步都要考慮三種可能：
nums[i]本身、curMax * nums[i]、curMin * nums[i]
Approaches
1. Brute Force (Enumerate All Subarrays) — O(n^2) / O(1)
- Idea: 枚舉所有子陣列的起點和終點，計算乘積並取最大值
- Time:
O(n^2) - Space:
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. DP with Min/Max Arrays — O(n) / O(n)
- Idea: 顯式建立兩個 DP 陣列
dpMax[i]與dpMin[i]，分別代表「以nums[i]結尾的最大／最小乘積」。狀態轉移：dpMax[i] = max(nums[i], dpMax[i-1]*nums[i], dpMin[i-1]*nums[i])，dpMin[i]對稱。 - Time:
O(n)- 每個位置 O(1) 轉移 - Space:
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)
- Idea: 同時維護以當前元素結尾的最大乘積和最小乘積，遇負數時交換
- Time:
O(n) - Space:
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 — 當正負性會影響結果時，需要同時追蹤最大和最小
- Key trick: 乘積問題中負數的處理：負 * 負 = 正，所以最小值可能在下一步變成最大值