Думаю почти каждый участник олимпиад хорошо знаком с алгоритмом нахождения подотрезка массива с наибольшей(наименьшей) суммой элементов за O(n).

Просматривая список задач по универским лабам, увидел в одном номере под разными буквами три, вроде бы схожие задачки. а)/b) классика — найти подотрезок с max/min суммой. А вот с) — найти подотрезок массива с суммой, наиболее близкой к нулю. Подумал немного и осознал, что не вижу решения ни за O(n), ни за n*log(n). То ли меня клинит и не вижу чего-то простого, то ли составитель методички отнесся халатно к расположению задач и оформлению требований к ним.

Собственно вопрос к сообществу CF — есть ли решение этой задачи с асимптотикой лучшей, чем квадратичная?

UPD за предложенное решение n*log(n) спасибо I_love_Tanya_Romanova. Остается вопрос о существовании линейного решения...