Giả sử chúng ta có một mảng gọi là nums, chúng ta phải tìm tích các phần tử của một mảng con liền kề trong một mảng (chứa ít nhất một số) có sản phẩm lớn nhất. Vì vậy, nếu mảng là [1,9,2,0,2,5], đầu ra sẽ là 18, vì mảng con liền kề [1,9,2] 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
- min_list:=danh sách các số kích thước và điền bằng 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([1,9,2,0,2,5]))
Đầu vào
[1,9,2,0,2,5]
Đầu ra
18