Изменения

Докажем, что перед обработкой блока и после его обработки сохраняется инвариант, что очередь <tex>B</tex> хранит ключи наилучших элементов для каждой длины всех возможных длин возрастающих подпоследовательностей, входящих в уже обработанную последовательность обработанной последовательности элементов.* Пусть перед обработкой блока <tex>C_i</tex> в очереди <tex>B</tex> хранятся ключи наилучших элементов, вычисленные соблюдается описанный инвариант для подпоследовательности последовательности <tex>S_{(i-1)m}=\{\pi_1,~\dots,~\pi_{(i-1)m}\}</tex>.* После слияния элементов очереди <tex>B</tex> и блока <tex>C_i^s</tex> получаем отсортированный список <tex>\mathtt{merged}</tex>. Cопоставив Сопоставив ключи элементам в списке, как их позиции в нём, выполняется будет выполняться условие <tex>(\pi_{u_j}<\pi_{u_k} \Longleftrightarrow \mathtt{key}(\pi_{u_j})<\mathtt{key}(\pi_{u_k}))</tex>, где <tex>\pi_{u_j},\pi_{u_k}\in \mathtt{merged}</tex>. Тогда справедливо утверждение, что любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов.* Во время обработки ключей элементов алгоритм <tex>\mathtt{LIS}</tex> работает только с очередью <tex>B</tex> и не зависит от предыдущих элементов последовательности, ключи которых не находятся в очереди. Так как на каждой итерации алгоритма <tex>\mathtt{LIS}</tex> сохраняется описанный инвариант для наилучших значений ключей элементов каждой длины возрастающих подпоследовательностей обработанной последовательности <tex>S_j</tex>, которые соответствуют ключам наилучших элементов <tex>S_j</tex>. , то , по завершению работы алгоритма <tex>\mathtt{LIS}</tex> на блоке <tex>C_i</tex> , результатом его работы будет очередь, в которой хранятся ключи, соответствующие наилучшим элементам каждой длины всех возможных длин возрастающих подпоследовательностей, входящих в <tex>S_{im}</tex>.* Таким образом, после обработки последнего блока, в очереди <tex>B</tex> будут храниться ключи наилучших элементов для каждой длины возрастающих подпоследовательностей последовательности <tex>S_n=S</tex>. Тогда последний элемент в очереди <tex>B</tex> соответствует наилучшему элементу длины НВП последовательности <tex>S</tex>, а так как в очереди <tex>B</tex> хранятся наилучшие элементы всех возможных длин всех возрастающих подпоследовательностей <tex>S</tex>, то размер очереди <tex>B</tex> равен длине НВП последовательности <tex>S</tex>.