ЕГЭОГЭ
Задания № 17, 24 · ЕГЭ

Префиксный максимум

Максимум на каждом префиксе массива
2 мин чтенияСложность: Обновлено 29 сентября 2026

Префиксный максимум — это наибольшее значение среди элементов массива от его начала до указанной позиции включительно. Он позволяет быстро узнать максимум для любого начального отрезка массива.

Префиксный максимумПрефикс — начало последовательности; значит, рассматривается отрезок массива, начинающийся с первого элемента.
Для массива \(a\) префиксный максимум на позиции \(i\) — это максимальное значение элементов \(a_0, a_1, \ldots, a_i\). Обычно его обозначают \(p_i\) или \(prefMax_i\). Для вычисления достаточно последовательно выполнить перебор массива, сохраняя самое большое встреченное значение.

Формула

Первый префиксный максимум равен первому элементу массива. Каждый следующий максимум сравнивает предыдущий результат с новым элементом:

\[prefMax_0=a_0,\qquad prefMax_i=\max(prefMax_{i-1},a_i)\quad (i\ge 1).\]

После построения массива префиксных максимумов ответ для позиции \(i\) находится за \(O(1)\): это просто \(prefMax_i\). Само построение занимает \(O(n)\) времени и \(O(n)\) памяти, если нужно сохранить все значения.

№
Пример

Пусть \(a=[3,1,7,4,9]\). Последовательно получаем префиксные максимумы: \([3,3,7,7,9]\). Например, максимум среди элементов с индексами от \(0\) до \(3\) равен \(prefMax_3=7\).

!
Не путайте с обычным максимумом

Префиксный максимум относится только к началу массива: \(a_0\ldots a_i\). Это не максимум на произвольном отрезке \([l,r]\). Для произвольных границ нужны другие способы обработки запросов к массиву; также префиксный максимум не следует путать с кумулятивной суммой, где элементы складываются, а не сравниваются.

Проверьте себя

Для массива \([5,2,8,6]\) чему равен префиксный максимум на позиции \(2\) при индексации с нуля?

Главное за минуту

Главное

  • Префиксный максимум на позиции \(i\) — максимум элементов от начала массива до \(i\) включительно.
  • Он вычисляется слева направо: новый результат — максимум предыдущего результата и текущего элемента.
  • Построение занимает \(O(n)\), а получение ответа для известной позиции — \(O(1)\).