สมมติว่าเรามีอาร์เรย์จำนวนเต็มที่เรียกว่า nums เราต้องหาอาร์เรย์ย่อยที่อยู่ติดกันภายในอาร์เรย์ (ที่มีอย่างน้อยหนึ่งหมายเลข) ซึ่งมีผลิตภัณฑ์ที่ใหญ่ที่สุด ดังนั้นหากอาร์เรย์เป็น [2,3,-2,4] เอาต์พุตจะเป็น 6 เนื่องจากอาร์เรย์ย่อยที่ต่อเนื่องกัน [2,3] จะมีผลคูณสูงสุด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- max_list :=รายการของขนาด nums และเติมด้วย 0
- min_list :=รายการของขนาด nums และเติมด้วย 0
- max_list[0] :=nums[0] และ min_list[0] :=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([2,3,-2,4,-5,-6,2]))
อินพุต
[2,3,-2,4,-5,-6,2]
ผลลัพธ์
240
