数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找最大子数组最小乘积
假设我们有一个数组 nums，我们需要找到 nums 的每个非空子数组的最大最小乘积。由于答案可能很大，请将其模 10^9+7 后返回。数组的最小乘积等于数组中的最小值乘以数组的和。例如，如果数组为 [4,3,6]（最小值为 3），则其最小乘积为 3*(4+3+6) = 3*13 = 39。
因此，如果输入类似于 nums = [2,3,4,3]，则输出将为 30，因为我们可以获得子数组 [3,4,3] 以最大化结果，因此 3*(3+4+3) = 3*10 = 30。
为了解决这个问题，我们将遵循以下步骤：
m := 10^9+7
stack := 新建一个栈
rsum := 0, res := 0
在 nums 的末尾插入 0
对于 nums 中的每个索引 i 和值 v，执行以下操作：
当栈不为空且栈顶元素对应的 nums 值大于等于 v 时，执行以下操作：
(index, val) := 栈顶元素，并将其从栈中弹出
arrSum:= rsum
如果栈不为空，则：
arrSum:= rsum - 栈顶元素的值
res:= res 和 (nums[index]*arrSum) 中的最大值
rsum := rsum + v
将 (i, rsum) 推入栈的末尾
返回 res 模 m
示例
让我们看看以下实现以更好地理解：
def solve(nums):
m = int(1e9+7)
stack = []
rsum = 0
res = 0
nums.append(0)
for i, v in enumerate(nums):
while stack and nums[stack[-1][0]] >= v:
index, _ = stack.pop()
arrSum=rsum
if stack:
arrSum=rsum-stack[-1][1]
res=max(res, nums[index]*arrSum)
rsum += v
stack.append((i, rsum))
return res % m
nums = [2,3,4,3]
print(solve(nums))输入
[2,3,4,3]
输出
30
更新于: 2021年10月8日
221 次查看
广告