Tổng mảng con lớn nhất với thuật toán Kadane trong Python
Tìm đoạn liên tiếp có tổng lớn nhất chỉ trong một lần duyệt, kể cả khi list có số âm.
- Tổng tốt nhất kết thúc tại mỗi vị trí
- Bắt đầu lại khi tổng đang chạy gây hại
- Thời gian O(n) và bộ nhớ O(1)
Nối dài đoạn hiện tại hay bắt đầu lại
Vấn đề
Đâu là chuỗi ngày tốt nhất của một cổ phiếu, chuỗi thắng dài nhất tính theo điểm, hay chặng đường lãi nhất của một chuyến đi? Tất cả đều là bài toán đoạn con có tổng lớn nhất. Thử mọi điểm đầu và điểm cuối thì chậm; thuật toán Kadane giải xong trong một lượt.
Hình dung đời thường
Thuật toán Kadane giống đi trên một con đường vừa nhặt vàng vừa phải trả phí. Bạn giữ một cái túi cho chặng đường hiện tại. Khi túi bị âm, mang nó theo chỉ thiệt thêm, nên bạn bỏ túi đó và bắt đầu lại. Bạn cũng nhớ lúc nào túi đầy nhất.
current = max(value, current + value)👛 Giữ túi cũ, hoặc bắt đầu lại nếu túi cũ tệ hơnbest = max(best, current)🏆 Nhớ chiếc túi đầy nhất từ trước tới giờcurrent = best = values[0]🚩 Bắt đầu bằng chặng đầu tiên6💰 Chặng tốt nhất: 4, -1, 2, 1Bài toán đoạn con lớn nhất (maximum subarray) tìm tổng lớn nhất của các phần tử liên tiếp trong list; thuật toán Kadane giải bài toán trong thời gian O(n) bằng cách theo dõi tổng tốt nhất kết thúc tại mỗi vị trí.
Những điểm quan trọng
currentlà tổng tốt nhất của một đoạn kết thúc ở giá trị hiện tại.current = max(value, current + value)bắt đầu đoạn mới khi đoạn cũ chỉ làm tổng nhỏ đi.best = max(best, current)giữ tổng tốt nhất từng gặp ở bất kỳ đâu.- Khởi tạo cả hai bằng
values[0]giúp list toàn số âm vẫn cho kết quả đúng.
Khi nào nên sử dụng?
- Giai đoạn tốt nhất trong chuỗi thời gian: lợi nhuận, điểm số, nhiệt độ.
- Học một ý tưởng quy hoạch động kinh điển chỉ cần một lượt duyệt.
- Câu hỏi phỏng vấn về mảng.
Khi nào chưa cần
- Cần biết điểm đầu và điểm cuối của đoạn tốt nhất: theo dõi thêm vị trí bên cạnh các tổng.
- Các giá trị không xếp theo một thứ tự có ý nghĩa: khi đó đoạn liên tiếp chẳng nói lên điều gì.
Code ví dụ
def maximum_subarray_sum(values):
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
Kết quả khi chạy
6
Giải thích code
Tại mỗi phần tử, biến current chọn giữa hai khả năng: bắt đầu một đoạn mới từ chính phần tử đó, hoặc nối tiếp đoạn trước bằng current + value. Biến best lưu tổng lớn nhất từng gặp. Với dữ liệu mẫu, đoạn [4, -1, 2, 1] cho tổng lớn nhất là 6. Thuật toán chạy trong O(n) và chỉ cần O(1) bộ nhớ.
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Lỗi hay gặp
Khởi tạo bằng 0
Với dữ liệu toàn số âm, hàm sẽ trả về 0, một đáp án sai.
current = best = 0
current = best = values[0]
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
- Sliding Window Maximum Report the maximum of every window of k numbers. Khó
- Largest Adjacent-Digit Product Take every contiguous window of span digits and multiply its digits. Trung bình