Да, за линейное время можно со стеком. А именно, посчитаем частичные суммы двух видов. Пусть L - минимальная длина интересующего нас отрезка. Тогда S1(i) = a(0) + ... + a(i), а S2(i) = a(0) + ... + a(i - L). Заметим, тогда, что для отрезка с концами в i и j (i >= j), среднее арифметическое значение будет равно X = (S1(i) - S2(j + L - 1)) / (i - j + 1). Сделаем замену t = j + L - 1, тогда получаем: X = (S1(i) - S2(t)) / (i - t + L). Нам требуется максимизировать X. Теперь у нас уже нет ограничения на минимальную длину отрезка, зато считаем мы уже не совсем среднее арифметическое значение.
Домножив обе части на знаменатель, имеем: S1(i) - X * (i + L) = S2(t) - X * t (*).
Слева и справа стоят уравнения прямых, где X - независимая переменная. Для фиксированного i нам требуется найти такое t, что точка пересечения соотв. прямых лежит как можно правее. Можно заметить, что оба угловых коэффициента отрицательные, причем у прямой с левой части он строго меньший, чем у прямой с правой части. Это значит, что если мы будем хранить нижнее огибающее множество прямых в левой части (lower envelope), то оптимальная точка пересечения будет достигаться при пересечении прямой S1(i) - X * (i + L) с одной из прямых, принадлежащих этому множеству. Поддерживая все прямые в стеке, можно за О(Н) вычислить эту точку пересечения для каждой из прямых. Достаточно знать, что задача нахождения нижнего огибающего множества прямых вида y = kx + l эквивалентна нахождению нижней цепи выпуклой оболочки точек вида (k, l).
Этот метод обобщается и для такой задачи: дан массив из N чисел, а также число L. Поступают запросы вида: "Дан отрезок чисел из этого массива, требуется в онлайне выдать подотрезок этого отрезка, длины не менее L, с максимальным средним арифметическим значением". Для обобщения алгоритма нужно сделать несколько наблюдений:
1. Как уже сказано выше, если зафиксировать правый конец отрезка и помнить нижнее огибающее множество всех прямых из правой части равенства (*), соответствующим числам, которые лежат левее правого конца, то для нахождения оптимального отрезка с этим правым концом, достаточно пересечь соотв. прямую из левой части равенства (*) с этим нижним огибающим множеством.
2. Аналогично для случая, когда зафиксирован левый конец отрезка и есть верхнее огибающее множество всех прямых из левой части равенства (*), соотв. числам справа от этого конца.
3. Если отрезок поделить на 2 части, для левой найти нижнее огибающее множество прямых из правой части (*), а для правых - верхнее огибающее множество прямых из левой части (*), а также предположить, что правый конец лежит в правой половине, а левый - в левой, то оптимальные концы можно найти, если пересечь эти 2 множества прямых. Пересекающиеся прямые и будут соответствовать концам оптимального отрезка. Можно показать, что точка пересечения всегда будет одна.
Можно пересекать такие множества за O(log^2(N)), делая 2 вложенных двоичных поиска: один по иксу, а второй по номеру соотв. отрезка или луча в каждом из множеств.
Вернемся к исходной задаче. Перед тем, как начинать отвечать на запросы, построим 2 дерева отрезков: в одном будут храниться прямые из левой части равенства (*), во втором - из правой. Оба они займут O(NlogN) памяти. Времени на построение уйдет столько же. Для каждой вершины из этих ДО найдем оптимальный отрезок, лежащий в них.
При ответе на запрос, мы поделим данный нам отрезок на O(logN) подотрезков, которым соответствуют вершины в деревьях отрезков. Для начала, найдем самый лучший подотрезок, целиком лежащий внутри одного из этих отрезков. Затем, можно пересечь все пары отрезков из разных деревьев описанным выше методом, и сравнить полученный ответ с уже найденным.
Последний этап занимает O(log^4(N)) времени. Но если вместо пересечения всех пар, зафиксировать один подотрезок, а затем последовательно идти от него вправо и сливать все огибающее множества в одно (можно неявно), то в сумме получится O(log^3(N)) времени.
Алгоритм вышел довольно сложный. Я давал практически такую же задачу на летние сборы в Петрозаводске 2011, так что если что-то непонятно - можно там в разборе глянуть.
