0
Предварительно обработать массив A в O (n log n), чтобы вы могли отвечать на запросы формы findmax (i, j): найти максимальное значение в интервале [i; j] (то есть максимальное значение среди элементов массива A [i], A [i + 1], ..., A [j]) в O (1)) времени на запрос.найти максимум подмассива
Дополнительный вопрос: Покажите, как выполнить предварительную обработку в O (n) времени, чтобы вы могли ответить на вышеуказанные запросы в O (log n).
Что вы пробовали? Сейчас похоже, что вы скопировали и вставляли этот вопрос дословно из набора проблем или веб-сайта, посвященного кодированию, что дает нам очень мало оснований хотеть помочь вам вообще. – templatetypedef
Я пробовал DP, и это вопрос олимпиады по информатике прошлого года. :) – 1234