最长上升子序列问题

最长LIS问题(\(O(n^2)\))

最长LIS(上升子序列)问题是一个经典的动态规划问题，问题描述如下“LIS是指从左到右的排序子序列，对于任意给定序列\(L\)求出它所有上升子序列(LIS)的最大长度。例如\([1,3,9,6,8]\)的一个最长LIS是\([1,3,6,8]\)，其长度为4”。这个问题的朴素算法可以是先求出原序列的全部子集(保持原有顺序)，然后遍历判断其是否为LIS并记录长度。

用\(F(k)\)表示“以\(L[k]\)结尾的最长LIS长度”。对满足\(F(k)\)的所有序列，若删去\(L[k]\)必是满足\(\{F(i) | i\in [0,k-1]\}\)中某问题的序列或空序列，且删去\(L[k]\)后的序列长度等于满足\(L[i]<L[k]\)的上述所有\(F(i)\)中的最大值。所以\(F(k)\)满足状态转移方程\(F(k) =1+max\{F(i) | i\in [0,k-1],L[i]<L[k]\}\)，无解则\(F(k)=1\)，且有边界\(F(0)=1\)。可以解出\(F\)的所有函数值与不同规模子问题间的状态转移，比如现有\((k’,i’)\)满足方程则说明存在满足\(F(k’)\)的序列去除末尾后是满足\(F(i’)\)的序列，即存在最后两位是\([i’,k’]\)的满足\(F(k’)\)的序列，以此类推利用边界条件最终得到解。然后用编程语言的数组表示\(F\)，按数组下标从小到大递推\(F[k]\)的所有值。递推出\(F\)的全部值后再求出\(F\)序列的最大值就是问题答案，该算法的时间复杂度为\(O(n^2)\)，其内层循环类似于顺序查找的过程。

最长LIS问题(\(O(nlg(n))\))

首先要遍历原序列\(L\)，如果遍历过程中\(L[k]\)一直单调递增，那么把遍历到的数追加给空数组\(G\)。如果在某\(L[i]\)处不满足单调递增，就在\([0…i-1]\)二分查找到符合排序的插入位置(但不插入)，把该位置的后继元素\(G[i’]\)值更新为\(L[i]\)。然后继续遍历，如果遍历到的数比当前\(G\)末位大则直接追加到\(G\)，否则按上述逻辑更新\(G\)中的某个数。这至多需要\(n\)次二分查找，所以其最坏时间为\(O(nlg(n))\)。但该算法的正确性不是特别明显，所以简单分析其正确性。

用\(F[i]\)表示\(L[0…i]\)子序列所有“LIS长度-该长度LIS最小的末尾值”的MAP，其KEY是小于等于\(i+1\)的从1开始的连续单调递增整数，其最大KEY是子序列的最长LIS长度。考虑用\(F[k]\)递推\(F[k+1]\)，首先要明确\(L[0…k+1]\)中包含的LIS只可能比\(L[0…k]\)更多，且多出来的部分末尾是\(L[k+1]\)，然后分情况来继续讨论：

1) 当\(L[k+1] > F[k][MAX]\)时，\(L[0…k+1]\)的LIS位数最大取\(MAX+1\)，其最小末尾等于\(L[k+1]\)，其他位数LIS的最小末尾值与\(L[0…k]\)的情况相同。

2) 当\(L[k+1] \leq F[k][MAX]\)时，\(F[k+1]\)与\(F[k]\)所对应的MAP的KEY部分完全相同。其中所有的小于\(L[k+1]\)的VALUE都保持相同。所有的大于等于\(L[k+1]\)的VALUE中最小的那个VALUE意味着\(L[k+1]\)的无法参与形成大于该KEY长度的LIS，所以此时只有该VALUE值会被更新成\(L[k+1]\)，其他的保持相同。