76
правок
Изменения
м
→Доказательство оптимальности
* Пусть перед обработкой элемента <tex>\pi_i</tex> соблюдается описанное выражение инварианта.
* Если <tex>\pi_i</tex> больше каждого элемента <tex>B</tex>, вычисленного для последовательности <tex>S_{i-1}=\{\pi_1,\pi_2,~\dots,~\pi_{i-1}\}</tex>, то он не может обновить любой из наилучших элементов, вычисленных ранее. С <tex>\pi_i</tex> можно составить возрастающую последовательность длины <tex>l+1</tex>, где <tex>l</tex> — длина НВП последовательности <tex>S_{i-1}</tex>, добавив <tex>\pi_i</tex> в конец этой НВП. Значит, <tex>\pi_i</tex> — наилучший элемент длины <tex>l+1</tex>. По предположению, размер <tex>B</tex> равен длине НВП последовательности <tex>S_{i-1}</tex>, потому что в <tex>B</tex> хранятся наилучшие элементы всех возможных длин возрастающих подпоследовательностей <tex>S_{i-1}</tex>. Тогда, добавив в конец очереди <tex>B</tex> элемент <tex>\pi_i</tex>, инвариант будет сохраняться.
* Иначе <tex>\pi_i</tex> будет наилучшим элементом для уже существующей длины. Заметим, что <tex>\pi_i</tex> может обновить только один элемент. В обратном случаеИначе, если <tex>\exists l_1,l_2\colon l_2>l_1</tex>, для которых <tex>\pi_i</tex> может быть наилучшим элементом, то существует такая подпоследовательность длины <tex>l_2</tex>, в которой <tex>\pi_i</tex> является наибольшим элементом, но из этой последовательности можно составить подпоследовательность длины <tex>l_1</tex>, в которой наибольший элемент меньше <tex>\pi_i</tex>, что противоречит предположению. Таким образом, <tex>\pi_i</tex> может обновить только наименьшее <tex>k\colon B_k > \pi_i</tex>. Тогда, заменив <tex>B_k</tex> элементом <tex>\pi_i</tex>, инвариант также будет сохраняться.
* После завершения алгоритма, в очереди <tex>B</tex> будут храниться наилучшие элементы для всех возможных длин возрастающих подпоследовательностей последовательности <tex>S</tex>. Тогда размер <tex>B</tex> равен длине НВП последовательности <tex>S</tex>.
}}
