題目描述:給定整數陣列 nums,找出乘積最大的連續子陣列,回傳其乘積。
解題思路:與最大子陣列和類似,但乘積有特殊性:兩個負數相乘得正。因此同時追蹤以當前元素結尾的「最大積」和「最小積」。當遇到負數時,兩者互換——原本的最小值乘以負數後可能成為最大值。每步更新全域最大值。
時間複雜度:O(n) — 單次線性掃描。
空間複雜度:O(1) — 只使用常數個變數。
1. Initialize maxProd = minProd = result = nums[0] 2. For i from 1 to n-1: a. If nums[i] < 0: swap(maxProd, minProd) b. maxProd = max(nums[i], maxProd * nums[i]) c. minProd = min(nums[i], minProd * nums[i]) d. result = max(result, maxProd) 3. Return result
雙重掃描 O(n):從左到右掃描一次,從右到左掃描一次,在遇到 0 時重置執行乘積。自然處理零;答案為兩次掃描的最大值。
DP 表 O(n) 空間:顯式存儲 dp_max[i] 和 dp_min[i] — 邏輯相同,使用更多記憶體。