Eng katta qism-massiv yig'indisi

$n$ ta butun sondan iborat massiv berilgan. Bo'sh bo'lmagan ketma-ket elementlar (qism-massiv) yig'indisining eng katta qiymatini toping.

Birinchi qatorda $n$ ($1 \le n \le 2 \cdot 10^5$). Ikkinchi qatorda $n$ ta butun son ($|a_i| \le 10^9$).

Bitta son — eng katta yig'indi.

$[l, r]$ yig'indisi $p_r - p_{l-1}$. Har bir $r$ uchun eng yaxshi $l$ — oldingi prefikslarning eng kichigi, demak javob $\max_r (p_r - \min_{j < r} p_j)$. Bu bitta o'tish, $O(n)$ (Kadane algoritmi ham aynan shu).

Hamma son manfiy bo'lsa ham qism-massiv bo'sh bo'lmasligi kerak: javob — eng katta element, $0$ emas. Misolda $3 - 2 + 5 + 3 = 9$. Yig'indi $2 \cdot 10^{14}$ gacha yetadi.

Manba: CSES, 1643-masala.