Модифицируем скользящее окно. Запихнем в него первые k чисел. Далее пойдем справа-налево в окне и если w[i-1] < w[i], тогда w[i-1] := w[i], то есть сделаем невозрастающий массив w (если смотреть слева-направо). Пример (k = 5): [10, 8, 6, 9, 7] -> [10, 9, 9, 9, 7]. Теперь в скользящем окне будем хранить не число, а пару (число, количество). Предыдущий пример перепишется в виде [(10, 1), (9, 3), (7, 1)]. Инвариант: в скользящем окне хранятся убывающие пары (по первому элементу) с суммой по вторым элементам, равным k, максимум находится в первой паре. Скользящее окно хранится либо деком, либо кольцевым массивом - будут удаления первого элемента.

Переходы: идем по массиву слева-направо, берем символ i. Уменьшаем на 1 количество первого элемента, если количество становится 0 - выкидываем, справа добавляем пару (a[i], 1). Теперь пока w[n - 2][0] <= w[n - 1][0] сливаем последние две пары в одну: (w[n - 1][0], w[n - 2][1] + w[n - 1][1]). Таким образом поддерживаем инвариант по убыванию, количеству и сохранением максимума в первом элементе.

Переходы амортизированно линейны.