在 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

以上是 在 Python 中查找最大子数组最小乘积的程序 的全部内容, 来源链接: utcz.com/z/354376.html

回到顶部