Задача с собеседования в Яндекс
Дается массив целых чисел a1, a2, a3, ..., an.
Отрезок назовем хорошим, если сумма чисел в ней равно нулю. Найдите максимальную по длине хороший подотрезок.
Например 1 2 -1 1 -1 -1
ответ 5.

Решение:
Давайте заведем префиксную сумму, то есть p[0] = 0, p[1] = a1, p[2] = a1 + a2, ...., p[n] = a1 + a2 + ... an. Ясно, что теперь сумму на подотрезке [l, r] мы можем узнавать через p[r] - p[l - 1]. Нас интересуют хорошие подотрезки, тогда разность должна быть равно нулю, то есть p[r] - p[l - 1] = 0, а именно p[r] = p[l - 1].

Давайте идти слева направо по префиксной сумме, пусть мы зафиксировали r, наша задача найти минимально возможную l, что p[r] = p[l]. Чтобы находить позицию l давайте во время прохода будем запоминать позиции первых вхождений для каждой суммы.

Работает за O(N) времени и O(N) памяти.
Псевдокод в комментариях: