Maksimal yig‘indili qism-massiv

O‘rta 1 s 256 MB0 kishi yechgan

$n$ ta butun sondan iborat massiv berilgan. Ketma-ket joylashgan (bo‘sh bo‘lmagan) elementlar qism-massivi orasidan yig‘indisi eng katta bo‘lganini toping va shu yig‘indini chiqaring.

Kiritish

Birinchi qatorda $n$ ( $1 \le n \le 2 \cdot 10^5$ ). Ikkinchi qatorda $a_1, \dots, a_n$ ( $|a_i| \le 10^9$ ).

Chiqarish

Eng katta yig‘indini chiqaring.

Namunalar

Kiritish 1

5
-2 1 -3 4 -1

Chiqarish 1

Kiritish 2

3
-5 -1 -8

Chiqarish 2

-1

Izoh

Yig‘indi $2 \cdot 10^{14}$ gacha bo‘lishi mumkin — 64-bitli tur kerak.

Manba: NolbirKod namuna