title
一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。
- 比方说，数组
[3,2,5]（最小值是2）的最小乘积为2 * (3+2+5) = 2 * 10 = 20。
给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 109 + 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 <= 1051 <= nums[i] <= 107
solution
单调栈，和柱状图求最大矩形一样。
class Solution:
def maxSumMinProduct(self, nums: List[int]) -> int:
n = len(nums)
mod = 10 ** 9 + 7
L, R = [-1] * n, [n] * n
stack = []
pre = [0] * (n + 1)
for i, v in enumerate(nums):
pre[i + 1] = pre[i] + v
while stack and nums[stack[-1]] > v:
R[stack[-1]] = i
stack.pop()
if stack:
L[i] = stack[-1]
stack.append(i)
ans = 0
for i, v in enumerate(nums):
l,r = L[i]+1, R[i]-1
ans = max(ans, (pre[r + 1] - pre[l]) * v)
return ans % mod