Thuật toán Python

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.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • 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)
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
-2
1
-3
4
-1
2
1
-5
4
4 - 1 + 2 + 1 = 6 là tổng lớn nhất của một đoạn liên tiếp.

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.

Từ con đường thu phí đến code
current = max(value, current + value)👛 Giữ túi cũ, hoặc bắt đầu lại nếu túi cũ tệ hơn
best = 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ên
6💰 Chặng tốt nhất: 4, -1, 2, 1
Kéo dài chuỗi khi còn có lợi; bắt đầu lại khi không còn.
Định nghĩa ngắn gọn

Bà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

  1. current là tổng tốt nhất của một đoạn kết thúc ở giá trị hiện tại.
  2. current = max(value, current + value) bắt đầu đoạn mới khi đoạn cũ chỉ làm tổng nhỏ đi.
  3. best = max(best, current) giữ tổng tốt nhất từng gặp ở bất kỳ đâu.
  4. 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ụ

Chạy code →
main.py
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]))
Lấy nút Run cho ví dụ này

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.

  1. 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.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đ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.
Chạy trong trình biên dịch Python →

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.

Sai
current = best = 0
Cách sửa
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.

Tất cả thử thách