Tích lớn nhất của mảng con (Maximum Product Subarray) trong Python

Giả sử chúng ta có mảng số nguyên nums, phải tìm mảng con liên tiếp trong mảng (chứa ít nhất một số) có tích lớn nhất. Ví dụ, nếu mảng là [2,3,-2,4], đầu ra là 6, vì mảng con liên tiếp [2,3] có tích lớn nhất.

Để giải quyết, ta làm theo các bước sau:

• max_list := danh sách kích thước nums, điền 0.

• min_list := danh sách kích thước nums, điền 0.

• max_list[0] := nums[0] và min_list[0] := nums[0].

• Với i từ 1 đến độ dài nums:

  • max_list[i] = max của max_list[i-1]*nums[i], min_list[i-1]*nums[i] và nums[i].
  • min_list[i] = min của min_list[i-1]*nums[i], nums[i], max_list[i-1]*nums[i].

• Trả về max của max_list.

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