状态定义:
$f[i]$记录以$a[i]$结尾的最长上升子序列长度
$f[i]$记录前$i$个数的最长上升子序列长度?
不行! $f[i]$与$f[i-1]$没有必然递推关系了。
$f[i]$记录以$a[i]$开头的最长上升子序列长度?
可以! 从后往前扫描。
初始条件:
$f[i]=1$
递推式: (状态转移方程)
如果$(a[i]>a[j])$
则$f[i]=\Large{max(f[i],f[j]+1)},1\le j<i$
时间复杂度:
$1+2+3+…+(n-1)$
$≈\frac{n(n-1)}{2}$,即$O(n^2)$
考虑新进来一个元素$a[i]$:
-
$\color{red}{大则添加}$:如果$a[i]>b[len]$,直接让$b[++len]=a[i]$。即$b[]$长度加$1$,且添加了一个新元素$a[i]$。
-
$\color{red}{小则替换}$:如果$a[i] \le b[len]$,就用$a[i]$替换掉$b[]$中$\color{red}{第一个\geq a[i]的元素}$。
假设第一个$\geq a[i]$的元素是$b[j]$,那么用$a[i]$换掉$b[j]$后,会使得$b[1…j]$这个上升子序列的结尾元素更小。对于一个LIS,其结尾元素越小就越可能变得更长。