โปรแกรมค้นหาผลิตภัณฑ์ขั้นต่ำของ subarray สูงสุดใน Python

สมมติว่าเรามีจำนวนอาร์เรย์ เราต้องหาผลคูณขั้นต่ำสูงสุดของอาร์เรย์ย่อยย่อยที่ไม่ว่างของ nums แต่ละอัน เนื่องจากคำตอบอาจมีขนาดใหญ่เพียงพอ ให้ส่งคืนเป็นโมดูล 10^9+7 ผลคูณขั้นต่ำของอาร์เรย์เท่ากับค่าต่ำสุดในอาร์เรย์คูณด้วยผลรวมของอาร์เรย์ ดังนั้นถ้าเรามี array เท่ากับ [4,3,6] (ค่าต่ำสุดคือ 3) จะมี min-product เท่ากับ 3*(4+3+6) =3*13 =39

ดังนั้น ถ้าอินพุตเป็นเหมือน nums =[2,3,4,3] เอาต์พุตจะเป็น 30 เพราะเราสามารถรับ subarray [3,4,3] เพื่อเพิ่มผลลัพธ์สูงสุด ดังนั้น 3*(3+4+ 3) =3*10 =30.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=10^9+7

• stack :=สแต็คใหม่

• rsum :=0, res :=0

• ใส่ 0 ต่อท้ายตัวเลข

• สำหรับแต่ละดัชนี i และค่า v เป็น nums ทำ

  • ในขณะที่ stack ไม่ว่างและ nums[index of top of stack]>=v, do

    • index, val) :=ด้านบนของ stack และเปิดขึ้นจาก stack

    • arrSum:=rsum

    • ถ้า stack ไม่ว่างก็

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

อินพุต

[2,3,4,3]

ผลลัพธ์

30