头部背景图片
Decaku 's Blog |
Decaku 's Blog |

关于最长上升子序列nlogn做法的证明

$ 笔者最近做题时,又遇到了常见的的最长上升子序列问题,之前在学习 \\
过程中对这个问题只是知道了做法,但是原理却一知半解,今天正好来 \\
整理一下。 $


$ LIS的定义:一段序列中最长的单调递增或单调不减的子序列。 $

$有关LIS的n^{2}的dp做法,网上已有相当多的解释,并且这种做法也比 \\
较直观,这里就不再赘述了。 $

$但是对于nlogn的优化算法,许多blog只给出了算法阐述,但是并未解释 \\
清楚原因,以下笔者将给出严格证明。 $

$先定义一下数组d,d[i]代表长度为i的上升子序列中最后一个元素的值, \\
若有多个长度为i的上升子序列,则d[i]取所有子序列最后一个元素的 \\
最小值。 $

$举个例子,对于序列1,4,3来说,长度为2的上升子序列有两个,分别 \\
是1,3和1,4;由于3比4小,根据定义,d[2]=3。 $

$那么很明显数组d的大小就是LIS的长度,只要维护d数组即可。 $

$以下证明d数组是单调不减的,即对于i \lt j,则有d[i] \leq d[j]。 $

$使用反证法证明: \\
假设存在i \lt j,d[i] \gt d[j]; \\
设长度为i的上升子序列为x_1,x_2 \cdots x_i; \\
设长度为j的上升子序列为y_1,y_2 \cdots y_i \cdots y_j; \\
则有y_i \leq y_j \lt x_i; \\
那么以子序列y_1 \cdots y_i的结尾y_i作为d[i]比x_i小。 \\
这不符合d数组的定义,所以假设不成立,证毕。 $

$具体维护d数组的过程为: 设a为要求LIS的序列,若a[i]比d[i-1]大, \\
更新d[i]为a[i]即可。否则,在d数组里寻找一个位置k,使得 \\
d[k-1] \lt a[i] \leq d[k],根据d数组的定义,所有长度为k的上升 \\子序
列最后一个元素的最小值应是a[i],使用a[i]更新d[k]即可。 $

$寻找k的过程可以二分,所以总复杂度为nlogn。$

avatar Decaku 很菜但也很想carry