Chương trình tìm tích lớn nhất của mảng con liên tiếp bằng Python

Cho mảng nums, tìm tích lớn nhất của một mảng con liên tiếp (ít nhất một phần tử).

Ví dụ: [1, 9, 2, 0, 2, 5] → 18 (mảng con [1, 9, 2]).

Quy trình giải quyết (Quy hoạch động)

1. Tạo hai mảng max_list và min_list kích thước len(nums).
2. Khởi tạo max_list[0] = min_list[0] = nums[0].
3. Với i từ 1 đến len(nums)-1:
   • max_list[i] = max(max_list[i-1]*nums[i], min_list[i-1]*nums[i], nums[i]).
   • min_list[i] = min(min_list[i-1]*nums[i], nums[i], max_list[i-1]*nums[i]).
4. Trả về max(max_list).

Ví dụ mã nguồn

class Solution:
    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_list[i-1]*nums[i], min_list[i-1]*nums[i], nums[i])
            min_list[i] = 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]))  # Output: 18

Đầu vào

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

Đầu ra

18