Đoạn con liên tiếp có tổng lớn nhất
Thuật toán Kadane là ví dụ đẹp nhất cho ý tưởng "trạng thái là thứ đang giữ": thay vì
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: python-basics, python-list-basics, python-loop-basics.
Nội dung đề bài
Mô tả bài toán
Thuật toán Kadane là ví dụ đẹp nhất cho ý tưởng "trạng thái là thứ đang giữ": thay vì thử mọi đoạn con, ta chỉ giữ tổng tốt nhất của đoạn con kết thúc ngay tại vị trí đang xét. Mỗi phần tử mới chỉ có hai lựa chọn: nối tiếp đoạn đang giữ, hoặc bắt đầu đoạn mới từ chính nó.
Yêu cầu
Viết hàm max_subarray_sum(values) trả về tổng lớn nhất của một đoạn con liên tiếp KHÔNG RỖNG trong values.
Công thức truy hồi (đã kiểm tra bằng tay): gọi cur là tổng lớn nhất của đoạn con kết thúc tại vị trí đang xét. Khởi tạo cur = best = values[0]; với mỗi phần tử x sau đó, cur = max(x, cur + x) rồi best = max(best, cur).
Quy ước nộp bài
Nộp hàm max_subarray_sum trong solution.py. Hệ thống gọi hàm trực tiếp bằng tham số từ khoá values và so giá trị trả về với kết quả đã cho; không đọc stdin và không in ra stdout.
Input
- values: danh sách số nguyên, độ dài từ 1 đến 20 phần tử.
Output
Một số nguyên là tổng lớn nhất tìm được.
Ràng buộc
- Đoạn con phải liên tiếp và phải có ít nhất một phần tử; đoạn rỗng không được tính là
0.
- Dãy toàn số âm vẫn phải trả về phần tử lớn nhất (ít âm nhất), không trả về 0.
- Danh sách luôn có ít nhất một phần tử, nên không cần xử lý danh sách rỗng.
Ví dụ 1
Input
max_subarray_sum(values=[-2, 1, -3, 4, -1, 2, 1, -5, 4])
Output
6
Ví dụ 2
Input
max_subarray_sum(values=[1, 2, 3, 4])
Output
10
Giải thích
Với values = [-2, 1, -3, 4, -1, 2, 1, -5, 4], đoạn 4 + (-1) + 2 + 1 = 6 là tốt nhất, nên hàm trả về 6. Với values = [-5, -2, -8], đoạn tốt nhất chỉ có một phần tử là -2, nên hàm trả về -2.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
