动态规划-其他DP-最长上升子序列

Posted by

定义

在一个序列中最长的单调递增的子序列,称为最长上升子序列(Longest Increasing Subsequence)。

求解算法

\(O(n^2)\)算法

思路

设\(a[1\ldots n]\)表示原序列,\(f[i]\)表示以第\(i\)个数结尾的LIS长度。
状态转移方程:
\[f[i]=max\{f[j]+1\},\quad j< i,\quad a[j]< a[i]\]
答案为\(max\{f[i]\},\quad 1\leq i \leq n\)。

实现

\(O(n\log n)\)算法

思路

设\(a[1\ldots n]\)表示原序列,\(f[i]\)表示长度为\(i\)的上升子序列的最小末尾,\(len\)表示当前LIS长度,可得\(f\)为递增数列。
每次读入一个数字\(k\),先与\(f[len]\)比较,如果大于则添加至\(f[++len]\),作为原来\(f[len]\)的后继。
否则在\(f\)中二分查找,找到\(f[i]< k\leq f[i+1]\),更新为\(f[i+1]\)为\(k\),即\(k\)比原来\(f[i+1]\)更优,可作为\(f[i]\)的后继。
答案为\(len\)。

实现

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注