Bob gửi cho Alice một dãy số nguyên gồm N 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 nếu:

Phần tử đầu tiên bằng phần từ cuối cùng (A₁ = AR);

• Tổng các phần tử của đ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°, 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.