Есть интересная задача (скорее всего хорошо известная), но к сожалению все, у кого я спрашивал, не знают как делать её быстрее чем за O(n ^ 2). Помогите бедному скатившемуся синему.

Задача: есть массив из целых чисел, надо найти отрезок [l, r] где величина sum(l, r) * len(l, r) будет максимальна. sum(l, r)= a[l] + a[l + 1] + ... + a[r], len(l, r) = r — l + 1. 1 <= n <= 10^5, -10^9 <= a[i] <= 10^9.

Ограничения могут быть и менее строгими, если существует какое-то быстрое и интересное решение.

Возможно это решается чем-то вроде кхт. Можно попробовать взять отрезок с наибольшей суммой и расширить его. Можно свести задачу к точкам на плоскости, где надо выбрать прямоугольник с наибольшей площадью, при чём левый нижний и верхний правый угол должны быть в одной из данных точек.