在 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。
示例
让我们看看以下实现以获得更好的理解-
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
热门推荐
1 训练狗狗憋尿
2 狗狗追踪训练
3 狗狗训练要多少钱
5 深圳狗狗训练
6 训练狗狗唤回
7 狗狗叫怎么训练
8 狗狗训练班
10 狗狗社会化训练
11 狗狗叫回训练
12 广州狗狗训练学校
13 狗狗训练躺下
14 狗狗随行训练
15 训练狗狗巡回
16 狗狗要怎么训练
17 狗狗喂食训练
18 训练狗狗躺下