用 Python 编写程序来查找最大子数组最小乘积

pythonserver side programmingprogramming更新于 2025/12/13 8:12:17

假设我们有一个数组 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 := a new stack
rsum := 0, res := 0
在末尾插入 0 nums
对于 nums 中的每个索引 i 和值 v，执行
- 当堆栈不为空且 nums[堆栈顶部的索引] >= v 时，执行
  - index, val) := 堆栈顶部并将其从堆栈中弹出
  - arrSum:= rsum
  - 如果堆栈不为空，则
    - arrSum:= rsum - 堆栈顶部的值
  - res:= res 和 (nums[index]*arrSum) 的最大值
- rsum := rsum + v
- 将 (i, rsum) 推送到堆栈末尾
返回 res mod 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))