Tổng đoạn con lớn nhất (thuật toán Kadane)
Tìm đoạn con liên tiếp có tổng lớn nhất là bài toán kinh điển dạy tư duy quy hoạch động: tại mỗi vị trí, ta chỉ cần biết đoạn tốt nhất kết thúc ở đây. Thuật toán Kadane giải trong…
Tiến độ của tôi ở bài này
Điểm đượ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: arrays-and-loops.
Nội dung đề bài
Mô tả bài toán
Tìm đoạn con liên tiếp có tổng lớn nhất là bài toán kinh điển dạy tư duy quy hoạch động: tại mỗi vị trí, ta chỉ cần biết đoạn tốt nhất kết thúc ở đây. Thuật toán Kadane giải trong O(N) thay vì thử mọi đoạn O(N2).
Yêu cầu
Đọc từ stdin: dòng 1 là N; dòng 2 là N số nguyên. In ra tổng lớn nhất của một đoạn con liên tiếp khác rỗng.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không truyền lời nhắc vào
input(). Lời nhắc sẽ bị in vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
Hai dòng: N và dãy N số nguyên.
Output
Một số nguyên: tổng đoạn con lớn nhất.
Ràng buộc
- 1 ≤ N ≤ 105; |ai| ≤ 109.
Ví dụ 1
Input
8
-2 1 -3 4 -1 2 1 -5Output
6
Đoạn `4, -1, 2, 1` có tổng 6, lớn nhất trong mọi đoạn liên tiếp.Ví dụ 2
Input
3
-5 -2 -8Output
-2
Mọi số đều âm nên đoạn tốt nhất chỉ gồm một phần tử lớn nhất, là -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.