Начнем со следующего наблюдения:
Пусть обозначает максимум последовательности , а обозначает его минимум. Если , то выбор является оптимальным.с 1 , . , , , a n m i n a 1 = m a x b 1 = b 2 = . , , = b n = ⌊ ( m a x + m i n ) / 2 ⌋maxa1,...,anmina1=maxb1=b2=...=bn=⌊(max+min)/2⌋
Почему это так? Итак, поскольку последовательность начинается с максимума, либо мы выбираем большое значение и страдаем большим отклонением от минимума последовательности (поскольку любое последующее значение должно быть больше или равно ), либо мы выбираем значение маленькое и страдаем от отклонение до . Среднее сводит к минимуму максимальное отклонение.b i b 1 b 1 m a xb1bib1b1max
Теперь мы можем попытаться обобщить это наблюдение для использования на общих последовательностях . Например, мы можем разбить любую последовательность на подпоследовательности, чтобы каждая из них начиналась с максимума соответствующей подпоследовательности.a1,...,an
Пример: разбивается на , и .((2,6,4,1,5,2,8,7,5,1)( 6 , 4 , 1 , 5 , 2 ) ( 8 , 7 , 5 , 1 )(2)(6,4,1,5,2)(8,7,5,1)
Учитывая это разбиение, теперь мы можем решить каждую из этих подпоследовательностей отдельно и получить присвоение , что, однако, может нарушить неубывающее условие. Это можно исправить без потери оптимальности.bi
Обратите внимание, что последняя подпоследовательность всегда содержит максимальный всей последовательности (в противном случае после нее будет другая подпоследовательность). Пусть - это значения, которые мы присвоили подпоследовательностям. Теперь, чтобы достичь в , мы начинаем со спины в и продвигаемся вперед. Если больше, чем , мы просто устанавливаем . Если оно меньше, мы сохраняем его. Затем мы продолжаем сравнивать с и так далее. Обратите внимание, что снижение любого до значенияш 1 , ш 2 , . , , , Ш K к ш 1 , . , , , w k w k w k - 1 w k w k - 1 : = w k w k - 2 w k - 1 w i w i + 1 w i w i + 1maxw1,w2,...,wkkw1,...,wkwkwk−1wkwk−1:=wkwk−2wk−1wiwi+1никогда не увеличивает отклонение, так как максимальное значение в подпоследовательности, назначенной с помощью , всегда ниже максимума в подпоследовательности, назначенной с помощью .wiwi+1
Этот алгоритм должен быть правильным, я думаю. Что касается времени работы, ключевым шагом является вычисление возрастающего максимума для подпоследовательностей, что возможно в ? Не уверен, где я .lO(n)l
Я думаю, что это должно быть выполнимо в O (N).
Возьмем аналогичную задачу. Для , 1 ≤ i ≤ n и d ≥ 0 найдите b i в не убывающем порядке, чтобы | a i - b i | ≤ d для всех i или покажи, что это невозможно. Это можно сделать в O (n), а с помощью бинарного поиска исходная проблема решается в O (n log l).ai bi |ai−bi|≤d
Теперь, если существует i ≤ j такое, что a_i - a_j> 2d, то решения не существует (поскольку ).bi≥ai−d,bj≤aj+d<ai−2d+d=ai−d≤bi
Но если a_i - a_j ≤ 2d для всех i ≤ j, то я думаю, что решение всегда будет найдено. Поэтому все, что нам нужно сделать, это найти m = max (a_i - a_j) для всех i ≤ j и выбрать d = floor ((m + 1) / 2). Этот максимум можно найти в O (n).
источник