Mảng con lớn nhất với thuật toán Kadane
Kadane quyết định tại mỗi vị trí nên tiếp tục đoạn cũ hay bắt đầu lại.
Mảng con lớn nhất với thuật toán Kadane là gì?
Kadane quyết định tại mỗi vị trí nên tiếp tục đoạn cũ hay bắt đầu lại.
Tìm đoạn liên tiếp có tổng lớn nhất.
Khi nào nên sử dụng?
- Rèn luyện tư duy giải quyết vấn đề và cấu trúc dữ liệu.
- Xử lý dữ liệu khi cần kiểm soát rõ từng bước của thuật toán.
- Chuẩn bị cho bài tập, kỳ thi và phỏng vấn lập trình.
Code ví dụ
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]))Kết quả dự kiến
6Cách hoạt động
Chỉ cần một lượt duyệt: thời gian O(n), bộ nhớ O(1).
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 sửa code theo các bài tập dưới đây để hiểu rõ cách hoạt động thay vì chỉ sao chép kết quả.
- Kiểm tra trường hợp rỗng, một phần tử và giá trị trùng lặp.
- In trạng thái sau từng bước để quan sát thuật toán.
- Đo thời gian với 100, 1.000 và 10.000 phần tử rồi so sánh cách giải khác.