Mô phỏng thuật toán Tích đoạn con lớn nhất

Maximum Product Subarray · Nhóm: Mảng

Tìm đoạn con liên tiếp có tích lớn nhất, xử lý được số âm bằng cách nhớ đồng thời tích lớn nhất và nhỏ nhất (Kadane cho tích).

Ý tưởng

Duyệt một lượt, tại mỗi i giữ curMax và curMin của đoạn kết thúc tại i.

Khi a[i] < 0, hoán vị curMax và curMin trước khi mở rộng, vì số âm lật vai trò lớn nhỏ.

Cập nhật curMax = max(a[i], a[i]·curMax) và curMin tương tự, rồi gộp curMax vào đáp số best.

Vì sao đúng

Khác bài tổng đoạn con: một số âm nhân với tích nhỏ nhất (rất âm) có thể thành lớn nhất · nếu chỉ nhớ curMax sẽ bỏ sót, nên phải theo dõi cả hai cực trị.

Mã Python

def max_product(a):
    cur_max = cur_min = best = a[0]
    for i in range(1, len(a)):
        x = a[i]
        if x < 0:
            cur_max, cur_min = cur_min, cur_max   # negative flips extremes
        cur_max = max(x, x * cur_max)
        cur_min = min(x, x * cur_min)
        best = max(best, cur_max)
    return best

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.