Giả sử chúng ta có một mảng số nguyên gọi là nums, chúng ta phải tìm mảng con liền kề trong một mảng (chứa ít nhất một số) có tích lớn nhất. Vì vậy, nếu mảng là [2,3, -2,4], đầu ra sẽ là 6, vì mảng con liền kề [2,3] có tích tối đa.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- max_list:=danh sách các số kích thước và điền bằng 0
- min_list:=danh sách các số kích thước và điền bằng 0
- max_list [0]:=nums [0] và min_list [0]:=nums [0]
- cho tôi trong phạm vi từ 1 đến độ dài là nums
- max_list [i] =max of max_list [i - 1] * nums [i], min_list [i - 1] * nums [i] và nums [i]
- min_list [i] =minof min_list [i - 1] * nums [i], nums [i], max_list [i - 1] * nums [i]
- trả về giá trị tối đa của max_list
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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]))
Đầu vào
[2,3,-2,4,-5,-6,2]
Đầu ra
240