Chương trình tìm sản phẩm tối thiểu của mảng con tối đa bằng Python

Giả sử chúng ta có một nums mảng, chúng ta phải tìm tích tối thiểu tối đa của mỗi mảng con không rỗng của nums. Vì câu trả lời có thể đủ lớn, hãy trả lại nó trong modulo 10 ^ 9 + 7. Tích tối thiểu của mảng bằng giá trị nhỏ nhất trong mảng nhân với tổng của mảng. Vì vậy, nếu chúng ta có một mảng giống như [4,3,6] (giá trị nhỏ nhất là 3) có tích tối thiểu là 3 * (4 + 3 + 6) =3 * 13 =39.

Vì vậy, nếu đầu vào giống như nums =[2,3,4,3], thì đầu ra sẽ là 30 vì chúng ta có thể nhận được mảng con [3,4,3] để tối đa hóa kết quả, vì vậy 3 * (3 + 4 + 3) =3 * 10 =30.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=10 ^ 9 + 7

• stack:=một ngăn xếp mới

• rsum:=0, res:=0

• chèn 0 vào cuối nums

• đối với mỗi chỉ số i và giá trị v tính bằng nums, thực hiện

  • trong khi ngăn xếp không trống và nums [chỉ mục của đầu ngăn xếp]> =v, do

    • index, val):=trên cùng của ngăn xếp và bật nó từ ngăn xếp

    • arrSum:=rsum

    • nếu ngăn xếp không trống, thì

      • arrSum:=rsum - giá trị của đầu ngăn xếp

    • res:=tối đa res và (nums [index] * arrSum)

  • rsum:=rsum + v

  • push (i, rsum) vào cuối ngăn xếp

• trả lại bản sửa đổi m

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[2,3,4,3]

Đầu ra

30