LIS(最长递增序列问题 nlogn)
P:0<=i<n;k是序列a[0:i]的最长递增子序列的长度;b[k]是序列a[0:i]中所有长度为k的递增子序列中最小结尾元素的值。在有i-1到i的循环中,当a[i] >= b[k]时,k = k+1,b[k] = a[i];当a[i] < b[k]时,应当在b[1:k]中找到一个位置j,使得b[j-1]<=a[i]<b[j],将b[j] = a[i],使得b序列满足性质.也就是说在b[1:k]序列中找到第一个比a[i]大的元素,将这个元素置为a[i]。为什么呢? 因为有b序列的性质可以得到,b[k]是序列a[0:i]中所有长度为k的递增子序列中最小结尾元素的值,那么如果存在b[j-1]<=a[i]<b[j],说明在a[0:i-1]中,长度为j-1的子序列的最小结束元素是b[j-1],长度为j的子序列的最小结束元素是b[j],i>j>j-1且b[j]>a[i]>b[j-1],所以在a[0:i]中长度为j的子序列的最小结束元素是a[i],因为它比b[j]小。从这也可以看出 b序列是有序的,可以用二分求解出a[i]放入的位置此算法关键:维护b序列的性质,二分求解
posted on 2009-08-07 21:01 newstar 阅读(302) 评论(1)  编辑 收藏 引用
Comments
只有注册用户登录后才能发表评论。