home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

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

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums เราต้องหาผลคูณขององค์ประกอบของอาร์เรย์ย่อยที่อยู่ติดกันภายในอาร์เรย์ (ที่มีอย่างน้อยหนึ่งหมายเลข) ซึ่งมีผลิตภัณฑ์ที่ใหญ่ที่สุด ดังนั้นหากอาร์เรย์คือ [1,9,2,0,2,5] เอาต์พุตจะเป็น 18 เนื่องจากอาร์เรย์ย่อยที่ต่อเนื่องกัน [1,9,2] จะมีผลคูณสูงสุด

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

  • max_list :=รายการของขนาด nums และเติมด้วย 0
  • min_list :=รายการของขนาด nums และเติมด้วย 0
  • min_list :=รายการของขนาด nums และเติมด้วย 0
  • สำหรับฉันอยู่ในช่วง 1 ถึงความยาวของ nums
    • max_list[i] =สูงสุดของ max_list[i - 1]*nums[i], min_list[i - 1]*nums[i] และ nums[i]
    • min_list[i] =minof min_list[i - 1]*nums[i], nums[i], max_list[i - 1]*nums[i]
  • คืนค่าสูงสุดของ max_list

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution(object):
   def maxProduct(self, nums):
      max_list = [0] * len(nums)
      min_list = [0] * len(nums)
      max_list[0] = nums[0]
      min_list[0] = nums[0]
      for i in range(1,len(nums)):
         max_list[i] = max(max(max_list[i-1]*nums[i],min_list[i-1]*nums[i]),nums[i])
         min_list[i] = min(min(min_list[i-1]*nums[i],nums[i]),max_list[i-1]*nums[i])
      return max(max_list)
ob1 = Solution()
print(ob1.maxProduct([1,9,2,0,2,5]))

อินพุต

[1,9,2,0,2,5]

ผลลัพธ์

18