1856. Maximum Subarray Min Product

Medium
Description

子陣列的 min-product 定義為子陣列最小值乘以子陣列元素總和。給定正整數陣列 nums，求所有非空子陣列的最大 min-product，結果對 10^9 + 7 取模。

Example:

Input: nums = [1,2,3,2] Output: 14

Intuition#

對每個元素，找到它作為最小值的最大範圍，用前綴和快速算出該範圍的總和。

  • 對每個 nums[i]，找到左邊和右邊第一個比它小的位置
  • 這段範圍內 nums[i] 就是最小值，用前綴和算出範圍內的總和
  • min-product = nums[i] * sum(left..right)
  • 用單調遞增堆疊高效地找到每個元素的左右邊界

Approaches#

1: Brute Force (TLE)#

  • 概念: 枚舉所有子陣列，計算 min-product
  • 時間複雜度: O(n^2)
  • 空間複雜度: O(1)
class Solution {
    fun maxSumMinProduct(nums: IntArray): Int {
        val MOD = 1_000_000_007L
        val n = nums.size
        val prefix = LongArray(n + 1)
        for (i in 0 until n) prefix[i + 1] = prefix[i] + nums[i]
        var ans = 0L
        for (i in 0 until n) {
            var minVal = nums[i]
            for (j in i until n) {
                minVal = minOf(minVal, nums[j])
                val sum = prefix[j + 1] - prefix[i]
                ans = maxOf(ans, minVal.toLong() * sum)
            }
        }
        return (ans % MOD).toInt()
    }
}

⭐2: Monotonic Stack + Prefix Sum#

  • 概念: 單調遞增堆疊找每個元素作為最小值的最大範圍，前綴和算區間和
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun maxSumMinProduct(nums: IntArray): Int {
        val MOD = 1_000_000_007L
        val n = nums.size
        val prefix = LongArray(n + 1)
        for (i in 0 until n) prefix[i + 1] = prefix[i] + nums[i]

        val left = IntArray(n)  // 左邊第一個 < nums[i] 的索引
        val right = IntArray(n) // 右邊第一個 < nums[i] 的索引
        val stack = ArrayDeque<Int>()

        for (i in 0 until n) {
            while (stack.isNotEmpty() && nums[stack.last()] >= nums[i]) stack.removeLast()
            left[i] = if (stack.isEmpty()) -1 else stack.last()
            stack.addLast(i)
        }
        stack.clear()
        for (i in n - 1 downTo 0) {
            while (stack.isNotEmpty() && nums[stack.last()] >= nums[i]) stack.removeLast()
            right[i] = if (stack.isEmpty()) n else stack.last()
            stack.addLast(i)
        }

        var ans = 0L
        for (i in 0 until n) {
            val sum = prefix[right[i]] - prefix[left[i] + 1]
            ans = maxOf(ans, nums[i].toLong() * sum)
        }
        return (ans % MOD).toInt()
    }
}

🔑 Takeaways#

  • Pattern: 單調堆疊 + 前綴和 — 對每個元素找到其作為極值的最大範圍
  • 關鍵技巧: 單調遞增堆疊可以在 O(n) 時間內找到每個元素左右第一個更小的元素；注意用 Long 避免溢位