Dãy số (THTB Vòng Khu vực 2021)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
Small
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bob gửi cho Alice một dãy số nguyên gồm \(N\) phần tử: \(A_1,A_2,...,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},...,A_R\) với \(1\leq L<R\leq 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_L=A_R\)).
  • 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.

Input

  • Dòng thứ nhất chứa số nguyên dương \(N\).
  • Dòng thứ hai chứa số nguyên \(A_1,A_2,...,A_N\text{ }(|A_i|\leq 10^9,1\leq i\leq N)\).

Output

  • 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.

Constraints

  • \(N\leq 10^5\)

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(N\leq 10^2\)
  • Subtask \(2\) (\(30\%\) số điểm): \(N\leq 10^3\)
  • Subtask \(3\) (\(30\%\) số điểm): \(N\leq 10^5\)

Example

Test 1

Input 
7
3 3 3 3 1 11 1
Output 
13

Bình luận