首页 > 代码库 > LIS n*log(n)的理解
LIS n*log(n)的理解
很多时候lis 用二分的方法比较方便 这里写一下他的原理
这里仅对严格的最长上升子序列做讨论
这里有两个数列 一个数列是 原串的数列 a1-an 另一个数列是最长上升子序列辅助数列 s数列的长度为 k, 是当前最长上升子序列长度
先来看看n*n的方法
dp[i]=max{dp[j]+1|j<i && ai>aj}
s数列是 对于当前的串 a1-ak 最长上升子序列为k j<=k 上升子序列长度为j的子串中,第j位最小的数为sj
用类似递推的思想 顺序从a1推到an
s0=-INF(INF 指无穷大)
对于当前的数ai
k=max{dp[j]|j>=1&&j<i}
s串长度为k
sx=min{aj| j>=1&&j<i&&dp[j]=x}
从a1顺序判断道an,到第i个位置 ,如果s数列满足上文的条件,s数列的长度为k 如果ai>sk ,即a1-a(i-1)中最长上升子序列长度为k,并且第k为最小的数为sk,那么说明到当前最长上升子序列可以增加一位。那么k+=1;s(k+1)=ai;
如果第i位ai<=sk 那么他不能是最长上升子序列增加一位 ,但是,他可能更新s数列,因为如果我们发现在s数列中存在s(j-1)<ai and sj>ai
sj就应该被ai更新,因为如果不更新,那么在a1-ai串中 上升子序列长度为j的子串中 第j为最小的不是sj, 而是ai ,所以这与s串的要求是不相符的。应该用ai替换sj 使sj满足条件
所以该算法的思路应该是
我们得到一个数ai
1 如果当前s 数列的长度为0 ,则 s1=ai;
2 如果当前s数列的长度为k,
如果ai>sk 那么 我们可以吧ai 加入到s数列的末尾
如果ai<=sk 。则说明在s数列中有一个数能被更新。找到一个位置j 使s(j-1)<ai并且s(j)>=ai 用ai替换sj。否则 s数列是不合法的
因为s数列是递增的 (自己可以证明),所以找到j位置是一个log级的算法 综合起来 这就是一个n*(logn)的算法
LIS n*log(n)的理解