What is the maximum subarray min-product problem?

The problem asks you to find the maximum min-product of any non-empty subarray, where the min-product is the product of the subarray's minimum value and its sum.

How can I solve the Maximum Subarray Min-Product problem efficiently?

Use a monotonic stack to manage the state of subarrays and a prefix sum array to calculate subarray sums efficiently. Maximize the min-product before applying modulo.

What are the main challenges of the Maximum Subarray Min-Product problem?

Key challenges include managing the monotonic stack correctly and ensuring the correct order of operations for the modulo operation after maximizing the min-product.

What is the time complexity of the best approach for this problem?

The optimal time complexity for solving this problem using a monotonic stack is O(n), where n is the length of the array.

How does GhostInterview help with the Maximum Subarray Min-Product problem?

GhostInterview provides guidance on using the right data structures, such as monotonic stacks and prefix sums, to solve the problem efficiently while avoiding common pitfalls.

#1856

Medium

auto_awesome栈·状态

LeetCode 题解工作台

子数组最小乘积的最大值

一个数组的最小乘积定义为这个数组中最小值乘以数组的和。比方说，数组 [3,2,5] （最小值是 2 ）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。给你一个正整数数组 nums ，请你返回 nums 任意非空子数组的最小乘积的最大值。由于答案可能很…

数组栈单调栈前缀和

题目描述

一个数组的 最小乘积 定义为这个数组中 最小值 乘以数组的和。

比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。

给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 10⁹ + 7 取余的结果。

请注意，最小乘积的最大值考虑的是取余操作之前的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。

子数组 定义为一个数组的连续部分。

示例 1：

输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。

示例 2：

输入：nums = [2,3,3,1,2]
输出：18
解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。
3 * (3+3) = 3 * 6 = 18 。

示例 3：

输入：nums = [3,1,5,6,4,2]
输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 * (5+6+4) = 4 * 15 = 60 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁷

lightbulb

解题思路

方法一：单调栈 + 前缀和

我们可以枚举每个元素 $nums[i]$ 作为子数组的最小值，找出子数组的左右边界 $left[i]$ 和 $right[i]$ 。其中 $left[i]$ 表示 $i$ 左侧第一个严格小于 $nums[i]$ 的位置，而 $right[i]$ 表示 $i$ 右侧第一个小于等于 $nums[i]$ 的位置。

为了方便地算出子数组的和，我们可以预处理出前缀和数组 $s$ ，其中 $s[i]$ 表示 $nums$ 前 $i$ 个元素的和。

那么以 $nums[i]$ 作为子数组最小值的最小乘积为 $nums[i] \times s[right[i]] - s[left[i] + 1]$ 。我们可以枚举每个元素 $nums[i]$ ，求出以 $nums[i]$ 作为子数组最小值的最小乘积，然后取最大值即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        left = [-1] * n
        right = [n] * n
        stk = []
        for i, x in enumerate(nums):
            while stk and nums[stk[-1]] >= x:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and nums[stk[-1]] > nums[i]:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)
        s = list(accumulate(nums, initial=0))
        mod = 10**9 + 7
        return max((s[right[i]] - s[left[i] + 1]) * x for i, x in enumerate(nums)) % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Assess if the candidate can optimize subarray operations using stacks.
question_mark
Look for the candidate's ability to balance time complexity with large input sizes.
question_mark
Test understanding of maximizing values before applying modulo operations.

warning

常见陷阱

外企场景

error
Forgetting to calculate the subarray sum efficiently using prefix sums.
error
Applying modulo too early, which can lead to suboptimal results.
error
Failing to correctly manage the stack to ensure minimum values are properly tracked.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations where negative numbers are allowed in the array.
arrow_right_alt
What if you had to compute the result for multiple subarrays at once?
arrow_right_alt
What changes if the array size is fixed or if a specific range of subarrays needs to be considered?

help

常见问题

外企场景

继续练习

#2281 巫师的总力量和 #1124 表现良好的最长时间段 #1793 好子数组的最大分数