MediumRating 2051
1856. Maximum Subarray Min-Product
arraystackmonotonic-stackprefix-sum
解題說明
Maximum Subarray Min-Product
題目描述：
給定一個正整數陣列 nums，子陣列的 min-product 定義為 子陣列最小值 × 子陣列元素之和。求所有非空子陣列中最大的 min-product（答案對 10⁹+7 取模）。
解題思路：
對於每個元素 nums[i]，找到以它為最小值的最大子陣列範圍，然後用前綴和快速計算該子陣列的元素之和。
- 單調遞增棧：對每個位置 i，用單調棧找到左邊第一個比它小的位置
left[i]和右邊第一個比它小的位置right[i]。則nums[i]作為最小值的最大子陣列為(left[i], right[i])（開區間）。 - 前綴和：預計算前綴和，O(1) 查詢任意子陣列的元素之和。
- 對每個 i 計算
nums[i] * sum(left[i]+1 ... right[i]-1)，取最大值。 - 注意：計算過程中使用
long long避免溢位，最後才對 10⁹+7 取模。
C++ 解法
複雜度分析
時間複雜度：O(n) — 前綴和 O(n)，兩次單調棧掃描各 O(n)，最終遍歷 O(n)。
空間複雜度：O(n) — 前綴和陣列、left/right 陣列和棧各需 O(n)。
虛擬碼
1. Compute prefix sum array 2. Use monotonic increasing stack to find: a. left[i] = index of nearest smaller element to the left of i (-1 if none) b. right[i] = index of nearest smaller element to the right of i (n if none) 3. For each index i: a. subarray sum = prefix[right[i]] - prefix[left[i] + 1] b. min-product = nums[i] * subarray sum c. Track maximum min-product 4. Return max min-product % (10^9 + 7)
其他解法
分治法 O(n log n)：類似歸併排序的思路，每次找到區間最小值，分別計算包含該最小值的最佳子陣列，再遞迴處理左右半邊。正確但實現複雜且常數因子較大。
暴力枚舉 O(n²)：枚舉所有子陣列，用線段樹或稀疏表 O(1) 查詢最小值和子陣列和。時間複雜度為 O(n²)，對大 n 不可行。
延伸思考
- 如果陣列中允許包含 0 或負數，如何修改演算法？
- 如果定義 max-product 為
子陣列最大值 × 子陣列和，是否可以用類似方法求解？ - 如何將單調棧方法推廣到二維矩陣（例如最大矩形問題）？