Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Trên web đọc dữ liệu từ bàn phím (stdin) và in ra màn hình (stdout).

Câu 3 (5,0 điểm) DÃY SỐ

Bob gửi cho Alice một dãy số nguyên gồm ~n~ phần tử: ~a_1, a_2, \ldots, a_n~, đây là thông tin về một kho báu. Một đoạn con ~(L, R)~ của dãy là một dãy gồm các phần tử liên tiếp ~a_L, a_{L+1}, \ldots, a_R~ với ~1 \le L < R \le n~, đoạn con ~(L, R)~ được gọi là chứa thông tin quan trọng nhất nếu:

• Phần tử đầu tiên và cuối cùng của đoạn con là bằng nhau ~(a_L = a_R)~;
• Tổng các phần tử của đoạn là lớn nhất.

Yêu cầu: hãy giúp Alice tìm đoạn con chứa thông tin quan trọng nhất.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên dương ~n~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(|a_i| \le 10^9, i = 1, 2, \ldots, n)~.
• Dữ liệu đảm bảo luôn có ít nhất một cặp ~L < R~ với ~a_L = a_R~.

Kết quả

• Một dòng chứa duy nhất một số nguyên là kết quả tìm được (tổng lớn nhất của đoạn con chứa thông tin quan trọng nhất).

Giới hạn

• Có 40% số test ứng với 40% số điểm của bài có ~n \le 10^2~;
• Có 30% số test khác ứng với 30% số điểm của bài có ~n \le 10^3~;
• Có 30% số test còn lại ứng với 30% số điểm của bài có ~n \le 10^5~.

Sample Input 1

7
3 3 3 3 1 11 1

Sample Output 1

13

Giải thích

Đoạn con chứa thông tin quan trọng nhất là ~(5, 7)~ có tổng lớn nhất là ~1 + 11 + 1 = 13~.

Sample Input 2

6
3 -2 -2 -3 -5 -5

Sample Output 2

-4

Giải thích

Đoạn ~(2, 3)~ có tổng ~-4~; đoạn ~(5, 6)~ có tổng ~-10~. Đáp án có thể âm.