Thuật toán Kadane: Tìm dãy con có tổng lớn nhất

Thuật toán Kadane là một thuật toán được sử dụng để tìm dãy con liên tiếp có tổng lớn nhất trong một mảng số nguyên. Đây là một thuật toán rất hiệu quả với độ phức tạp thời gian O(n), với n là độ dài của mảng.

Dưới đây là một phiên bản cơ bản của thuật toán Kadane viết bằng Python:

def max_subarray_sum(arr):
    max_current = max_global = arr[0]

    for i in range(1, len(arr)):
        max_current = max(arr[i], max_current + arr[i])

        if max_current > max_global:
            max_global = max_current

    return max_global

Cách hoạt động của thuật toán Kadane như sau:

1. Khởi tạo hai biến: max_current và max_global bằng giá trị đầu tiên của mảng arr.
2. Duyệt qua mảng từ phần tử thứ 2 trở đi.
3. Ở mỗi bước duyệt, cập nhật max_current bằng giá trị lớn nhất giữa phần tử hiện tại và tổng của max_current và phần tử hiện tại. Ý tưởng là chúng ta luôn giữ lại dãy con có tổng lớn nhất tại mỗi bước.
4. So sánh max_current với max_global và cập nhật max_global nếu max_current lớn hơn.

Kết quả trả về là max_global, tức là tổng lớn nhất của một dãy con liên tiếp trong mảng arr.

Ví dụ:

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = max_subarray_sum(arr)
print(result)  # Kết quả sẽ là 6 (dãy con liên tiếp là [4, -1, 2, 1])

Thuật toán Kadane rất hữu ích trong nhiều bài toán liên quan đến tối ưu hóa tổng của các phần tử trong mảng, chẳng hạn như tìm dãy con có tổng lớn nhất, xác định tập con không chồng lấn có tổng lớn nhất, và nhiều bài toán khác.