giúp e với ạ ----- Nội dung ảnh ----- Bob gửi cho Alice một dãy số nguyên gồm M phần tử: A1, A2, ..., AN, đâ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 AL, AL+1, ..., AR với 1 ≤ L < R ≤ N, đoạn con (L, R) được gọi là chứa thông tin quan trọng nhất:
- Phần tử đầu tiên bằng phần tử cuối cùng (AL = AR); - Tổng các phần tử trong đoạn là lớn nhất có thể.
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 từ thiết bị vào chuẩn:
- Dòng thứ nhất chứa số nguyên dương N; - Dòng thứ hai chứa N số nguyên A1, A2, ..., AN (|Ai| ≤ 10^9, 1 ≤ i ≤ N).
Kết quả: Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng của đoạn con chứa thông tin quan trọng nhất.
Ràng buộc: - Có 40% số test ứng với 40% số điểm của bài có N ≤ 10^2. - Có 30% số test khác ứng với 30% số điểm của bài có N ≤ 10^3. - Có 30% số test còn lại ứng với 30% số điểm của bài có N ≤ 10^5.
