09_Segment_zbira_nula

Neka je dat niz od n celih brojeva. Naći dužinu najdužeg segmenta niza čiji zbir elemenata iznosi nula.

Napomena: Zadatak se može rešiti u vremenskoj složenosti O(nlog n) i prostornoj složenosti O(n).

Ulaz

Sa standardnog ulaza se učitava ceo broj n (1 ≤ n ≤ 10⁶), a zatim niz od n celih brojeva iz opsega [−10⁹, 10⁹].

Izlaz

Na standardni izlaz ispisati dužinu najdužeg segmenta niza čiji zbir elemenata iznosi nula. Ako ne postoji segment sa sumom nula, ispisati 0.

Primer

Ulaz

8
1 2 -2 4 -4 3 -1 2

Izlaz

5

Objašnjenje

Segment niza [-2, 4, -4, 3, -1] je najduži segment čiji zbir elemenata iznosi nula, i on je dužine 5.