Chương trình Python giải bài toán mảng con lớn nhất (Kadane)

Thuật toán Kadane tìm mảng con liên tiếp có tổng lớn nhất trong O(n).

Ví dụ

def max_subarray(arr):
    max_ending = max_so_far = arr[0]
    start = end = 0
    temp_start = 0

    for i in range(1, len(arr)):
        if max_ending > 0:
            max_ending += arr[i]
        else:
            max_ending = arr[i]
            temp_start = i

        if max_ending > max_so_far:
            max_so_far = max_ending
            start = temp_start
            end = i

    return start, end, max_so_far

nums = list(map(int, input("Nhập dãy số: ").split()))
l, r, s = max_subarray(nums)
print(f"Mảng con lớn nhất: index {l} đến {r}, tổng = {s}")

Kết quả

Nhập dãy số: 2 5 7 12 6 8
Mảng con lớn nhất: index 0 đến 5, tổng = 40

Giải thích

• max_ending: tổng lớn nhất của mảng con kết thúc tại i.
• Nếu max_ending > 0, mở rộng mảng con; nếu không, bắt đầu mới tại i.
• max_so_far: tổng lớn nhất thấy được cho đến nay.
• Theo dõi start, end của mảng con tối ưu.
• Độ phức tạp O(n), O(1) bộ nhớ.