Thuật toán Kadane: Tổng đoạn con liên tiếp lớn nhất trên mảng vòng tròn

Mục tiêu kiến thức

• Hiểu thuật toán Kadane tìm đoạn con có tổng lớn nhất trên mảng tuyến tính trong O(N).
• Mở rộng lên mảng vòng tròn (phần tử cuối A_N kế tiếp phần tử đầu A₁):
• Trường hợp 1: Đoạn con tối ưu không quấn vòng (chính là Kadane tiêu chuẩn).
• Trường hợp 2: Đoạn con tối ưu quấn vòng ⇒ Tổng mảng trừ đi đoạn con có tổng nhỏ nhất không quấn vòng.
• Xử lý trường hợp đặc biệt: Tất cả các phần tử trong mảng đều âm.

Mô tả bài toán

Cho một mảng gồm N số nguyên A₁, A₂, …, A_N được xem như một vòng tròn khép kín. Hãy tìm một đoạn con liên tiếp không rỗng có tổng các phần tử lớn nhất.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và 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.

Ràng buộc

• 1 ≤ N ≤ 10⁵.
• Thời gian: 1000ms. Bộ nhớ: 256MB.