gistfile1.txt

Решение №1, популярное: будем содержать элементы окна в деке, максимум в котором научимся получать за О(1).
Наблюдение№1: пусть в деке {q1, q2 ... qm} qi <= qj где i < j. Тогда мы можем удалить qi из дека, т.к. оно никогда не повлияет на максимум.
Наблюдение№2: дек, в котором не наблюдается ситуации из наблюдения№1, упорядочен по убыванию.
Наблюдение№3: максимальный элемент в этом деке равен q1

Алгоритм теперь понятен: чтобы вставить новый элемент A в дек, сначала удаляем все те из головы, что меньше или равны A, затем вставляем А в голову.
Чтобы удалить элемент из дека просто удаляем элемент из дека :) Ну и каждый раз возвращаем максимум, равный q1.
Теперь сложность: несмотря на то, что при вставке мы можем сделать и линейный проход (напр, вставляем 11 в {10 9 8 7 6 5 4 3 2 1} ), амортизационно сложность будет O(N), т.к. каждый элемент мы вставим в дек один раз и удалим тоже максимум один раз.

Решение №2, автор Ваня "dfyz" Комаров из Яндекса: мысленно разобьем наш массив на подмассивы длиной M, т.е. {a1...am}, {a(m+1) ... a(m*2)}, ...
Таких массивов будет floor(N/M). Теперь для каждого из таких массивов посчитаем максимумы на всех его префиксах и суффиксах.
При любом положении окна оно будет пересекать максимум два таких массива. Например, {a1...am}, {a(m+1) ... a(m*2)} при окне a3...a(m + 3). Ответ в этом случае выражается как максимум из максимума на префиксе одного массива и суффиксе другого, т.е. max(sufmax[a3..am], prefmax[a(m+1)..a(m+3)]).
Каждый из таких массивов, понятное дело, предпросчитывается за линейное время от длины этого массива и суммарно мы затратим O((N/M)*M)=O(N) операций.

Решение №3, автор http://109.livejournal.com/

Воспользуемся ограниченностью машинного слова и будем добавлять в trie битовые(или не битовые, а какие-нибудь другие) представления наших чисел. Чтобы учитывать повторяющиеся числа -- храним в терминальных вершинах их количество. Добавление, удаление и нахождение максимума делаются за O(1) прохождением по trie сверху вниз.

Код такой:
trie.add(a[j]);
if (j >= M) 
trie.remove(a[j-M]);
if (1+j >= M) 
result[1+j-M]=trie.getMax();

add вставляет элемент, если его нет, иначе инкрементирует каунтер. remove наоборот.