~/algor $ cat masalalar/nollashgan-qism-massiv
Nollashgan Qism Massiv
Iqbolshoh yangi neyrotarmoq algoritmida ma'lumotlar oqimini balanslash ustida ishlamoqda.
Unga N ta butun sondan iborat $A = [A_1, A_2, \dots, A_N]$ massiv berilgan. Massivdagi sonlar musbat, manfiy yoki nol bo'lishi mumkin.
Balanslashgan oraliq deb, massivning shunday bo'sh bo'lmagan ketma-ket qism massivi $A[L \dots R]$ ($1 \le L \le R \le N$) ga aytiladiki, undagi barcha elementlar yig'indisi aynan 0 ga teng bo'lsin:
$$\sum_{i=L}^{R} A_i = 0$$
Iqbolshoh eng katta balanslashgan oraliqni topmoqchi. Sizning vazifangiz — yig'indisi 0 ga teng bo'lgan eng uzun ketma-ket qism massivning uzunligini (R - L + 1) aniqlash. Agar bunday qism massiv mavjud bo'lmasa, 0 chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda bitta butun son: N ($1 \le N \le 2 \cdot 10^5$) kiritiladi.
Ikkinchi qatorda N ta butun son: $A_1, A_2, \dots, A_N$ ($-10^9 \le A_i \le 10^9$) kiritiladi.
Chiquvchi ma'lumotlar
Yig'indisi 0 bo'lgan eng uzun qism massiv uzunligini chiqaring. Agar mavjud bo'lmasa, 0 chiqaring.
Izoh
1-namuna:
6
1 2 -3 4 -4 5 -> 5 (1 dan 5 gacha: 1+2-3+4-4 = 0)
2-namuna:
4
5 -2 3 1 -> 0
3-namuna:
5
0 0 0 0 0 -> 5
Misollar
6 1 2 -3 4 -4 5
5
4 5 -2 3 1
0
5 0 0 0 0 0
5
Yechim tahlili
Avval o'zingiz yechib ko'ring — tahlilni o'qish o'rganishga yordam beradi, lekin javobni tayyor beradi.
unordered_map) da saqlab boramiz:
- Boshida map[0] = 0.
- Har bir $i = 1 \dots N uchun P_i$ ni hisoblaymiz.
- Agar P_i map'da avval uchragan bo'lsa, uzunlik $i - map[P_i]$ bo'ladi va maksimum uzunlikni yangilaymiz.
- Aks holda, P_i birinchi marta uchragani uchun map[P_i] = i deb yozib qo'yamiz.
$N \le 2 \cdot 10^5, vaqt murakkabligi O(N), xotira O(N)$. Yig'indilar $2 \cdot 10^{14}$ gacha borishi mumkinligi sababli long long ishlatish shart.