Muallif: __thecrash__
A. Maksimal bo'lak yig'indisi
Vaqt limiti: 2000 ms Xotira limiti: 256 mb
Sizga \(n\) ta butun sondan iborat \(a_1, a_2, \dots, a_n\) massiv berilgan. Shu massivning bo'sh bo'lmagan ketma-ket bo'lagini (subarray, ya'ni \(a_l, a_{l+1}, \dots, a_r\) ko'rinishidagi, \(1 \le l \le r \le n\)) tanlang, shunday qilib uning elementlari yig'indisi eng katta bo'lsin. Shu maksimal yig'indini toping.
Diqqat: Bo'lak bo'sh bo'lishi mumkin emas — kamida bitta element tanlanishi shart (massivdagi barcha sonlar manfiy bo'lsa ham).
Kiruvchi ma'lumotlar
Birinchi qatorda \(n\) (\(1 \le n \le 10^6\)) soni beriladi.
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \dots, a_n\) (\(-10^9\le a_i \le 10^9\)) beriladi.
Chiquvchi ma'lumotlar
Yagona qatorda — maksimal bo'lak yig'indisini chiqaring.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
5 1 -2 3 4 -1 |
7 |
2 |
4 -5 -2 -8 -1 |
-1 |