Tổng quan
Thuật Toán Kadane tìm tổng lớn nhất của một dãy con liên tiếp chỉ trong một lượt. Quy tắc cốt lõi gói trong một dòng: tại mỗi phần tử, quyết định xem nên kéo dài đoạn đang chạy hay bỏ nó và bắt đầu lại từ đây.
Nhận xét khiến nó đúng là: một tổng đang chạy đã hóa âm thì không bao giờ giúp được bất cứ thứ gì đứng sau nó. Phần phía sau chắc chắn có lợi hơn nếu bắt đầu lại từ số không. Nên ngay khi tổng chạy tụt xuống dưới 0, nó bị vứt đi, và thuật toán không bao giờ phải nhìn lại phía sau — đó là cách một phép vét cạn O(n³) trên mọi dãy con thu về một lượt quét O(n) với hai biến.
Thuật Toán Kadane hoạt động thế nào?
- Khởi tạo cả tổng đang chạy lẫn tổng tốt nhất bằng phần tử đầu tiên — không phải bằng 0, vì như vậy sẽ sai với đầu vào toàn số âm.
- Chuyển sang phần tử kế tiếp và hỏi: bản thân nó có lớn hơn khi cộng vào tổng đang chạy không?
- Nếu có, đoạn trước đó đang kéo nó xuống — bỏ đoạn đi và cho tổng đang chạy chỉ bằng chính phần tử này.
- Nếu không thì kéo dài: cộng phần tử vào tổng đang chạy.
- Cập nhật tổng tốt nhất nếu tổng đang chạy vừa vượt qua nó, rồi tiếp tục tới hết mảng.
Khi nào nên dùng?
- Tìm khoảng tốt nhất trong một chuỗi thời gian: đoạn lãi cao nhất, đoạn sụt giảm sâu nhất, khoảng làm việc hiệu quả nhất.
- Bước tìm dãy con lớn nhất bên trong phiên bản hai chiều, khi nó chạy một lần cho mỗi cặp ranh giới cột.
- Xử lý tín hiệu và ảnh, khi phải định vị vùng phản hồi liên tiếp mạnh nhất trong một lượt trên dữ liệu chảy liên tục.
- Một minh họa chuẩn mực rằng một quyết định tham lam cục bộ có thể chứng minh được là tối ưu — khác với bài đổi tiền, nơi nó không phải vậy.
Phân tích độ phức tạp
Thời gian là O(n) với một lượt duy nhất và không vòng lặp lồng nhau, còn bộ nhớ là O(1) vì chỉ giữ tổng đang chạy và tổng tốt nhất. Nó cũng là thuật toán trực tuyến: mỗi phần tử được tiêu thụ một lần và không bao giờ được xem lại, nên chạy được trên luồng dữ liệu mà cả mảng chưa từng nằm trong bộ nhớ. Muốn lấy ra chính dãy con đó chứ không chỉ tổng của nó thì tốn thêm hai số nguyên cho chỉ số đầu và cuối.
Câu hỏi thường gặp
Chuyện gì xảy ra khi mọi số đều âm?
Đáp án phải là phần tử âm ít nhất, và thuật toán trả về đúng nó — với điều kiện bạn khởi tạo bằng phần tử đầu chứ không phải 0. Khởi tạo bằng 0 sẽ khiến nó báo 0, tức một dãy con rỗng, và đây là lỗi phổ biến nhất của thuật toán này.
Làm sao lấy ra chính dãy con đó?
Theo dõi một chỉ số bắt đầu tạm, đặt lại mỗi khi đoạn được khởi động lại, và chốt chỉ số đầu-cuối đúng lúc tổng tốt nhất được cải thiện. Việc này không tốn thêm gì về mặt bậc.
Nó có mở rộng lên hai chiều được không?
Có. Cố định một cặp ranh giới cột trái và phải, nén mỗi hàng giữa chúng thành một tổng duy nhất, rồi chạy Kadane dọc theo cột đã nén đó. Xét hết mọi cặp cột cho ra O(số hàng · số cột²), vẫn tốt hơn vét cạn rất nhiều.