Tổng dãy con liên tiếp lớn nhất trên mảng vòng

Buổi 03 — Mảng 1 Chiều
Points
33
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho mảng vòng số nguyên $A$ gồm $n$ phần tử (phần tử $A_n$ được coi là liền kề trước $A_1$). Hãy tìm tổng lớn nhất của một dãy con liên tiếp khác rỗng trên mảng vòng này (mỗi phần tử chỉ được chọn tối đa một lần).

Dữ liệu vào

Dòng đầu chứa số nguyên $n$. Dòng thứ hai chứa $n$ số nguyên $A_1, A_2, \dots, A_n$.

Dữ liệu ra

Một số nguyên duy nhất là tổng lớn nhất tìm được.

Ví dụ

Input

3
5 -3 5

Output

10
Giới hạn

$1 \le n \le 2 \cdot 10^5$, $|A_i| \le 10^9$.

Draft saved