首页 > 其他 > 详细

lrj 9.4.1 最长上升子序列 LIS

时间:2016-08-22 19:42:06      阅读:145      评论:0      收藏:0      [点我收藏+]

p275

d(i)是以Ai为结尾的最长上升子序列的长度

 

《算法竞赛入门经典-训练指南》p62 问题6 提供了一种优化到 O(nlogn)的方法。

 在O(nlogn)的算法分析中(从“假设已经计算出的两个状态...”开始),

 用g(i)表示d值为i的最小状态编号,状态编号就是数组下标

 g(1) <= g(2) <= g(3) <= ... <= g(n)

 可以用反证法:

 假设 i < j, g(i) > g(j)

 g(j)代表 d(x) = j 的最小 x,对应的LIS的长度为j,设这个LIS为LISj

 g(i)代表 d(y) = i 的最小 y,对应的LIS的长度为i

 LISj有j个成员,其他取i个成员是一个LIS,长度为i,这个LIS的最后一个成员的下标 < g(j) < g(i),而 g(i) 应该是长度为i的LIS的最小下标,所以矛盾,得证 #

 

 

 

 

《挑战程序设计竞赛》p64 也有类似分析

 

lrj 9.4.1 最长上升子序列 LIS

原文:http://www.cnblogs.com/patrickzhou/p/5796475.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!