|
|
| 最长递增子序列 |
|
|
|
|
Sure之动态规划篇
问题
给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能
乱）。例如：给定一个长度为6的数组A{5，6，7，1，2，8}，则其最长的单调递增
子序列为{5，6，7，8}，长度为4.
解法1：最长公共子序列法
这个问题可以转换为最长公共子序列问题。如例子中的数组A{5，6，7，1，2，8}，则
我们排序该数组得到数组A‘{1，2，5，6，7，8}，然后找出数组A和A’的最长公共子
序列即可。显然这里最长公共子序列为{5,6,7,8}，也就是原数组A最长递增子序列。最长
公共子序列算法在算法导论上有详细讲解，这里简略说下思想。
假定两个序列为X={x1,x2,...,xm}和Y={y1,y2,...,yn)，并设Z={z1,z2,...,zk}为X和Y
的任意一个LCS。
1）如果xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的一个LCS。
2）如果xm!=yn,则zk!=xm蕴含Z是Xm-1和Y得一个LCS。
3）如果xm!=yn,则zk!=yn蕴含Z是X和Yn-1的一个LCS。
解
设长
长度
有位
我们
例如
所以
Cpp代
法2：动
长度为N的数
度为L(j)，则
位置i(从0到
们遍历所有的
如给定的数组
以该数组最长
代码
1.#include
2.usingna
3.#define
4.intlis(
5.{
6.int
7.for
8.
9.
10.for
11.
12.
longest
13.
增子序列
14.
15.
16.}
17.int
18.for
19.
20.
21.}
22.retu
23.}
24.intma
25.{
26.int
27.int
28.cout
29.retu
30.}
动态规划
数组为{a0，a
L(j)={max(L
到j-1)，找出满
的L(j)（从0到
组为{5，6，7，
长递增子序列
mespacestd
len(a)(si
intarr[],
longest[le
(inti=0;
longest[i]
(intj=1;j
for(inti=
if(ar
[i]+1这个条件
lo
长度
}
}
max=0;
(intj=0;j
cout<<"lo
if(longest
rnmax;
in()
arr[]={1
ret=lis(a
<<"maxi
rn0;
Sure
划法（时
1,a2,...an-
(i))+1,i
满足条件a[i]<
N-1），找出最
，1，2，8}，
列长度为4，序
>
;
zeof(a)/s
intlen)
n];
i
=1;
0;i
r[j]>arr[i]
件，不能省略
ngest[j]=
ngest["<<
[j]>max)
,4,5,6,
rr,len(ar
ncrementsu
之动态规
时间复杂
1)，则假定
且a[i]
a[j]的L(i)，
最大值即为最
则L(0)=1,L
序列为{5，6
izeof(a[0])
{
+){
&&longest
。
longest[i]
{
j<<"]="
max=long
2,3,8};/
r));
bstringlen
划篇
杂度O
以aj结尾的
也就是说，
求出max(L
最大递增子序
(1)=2,L(2)=
，7，8}。算
)//数组长度
[j]
+1;//计算
<
est[j];//
/测试数组
="<
(N^2))
的数组序列的
我们需要遍
(i))+1即为L
序列。时间复杂
3,L(3)=1,L
算法代码如下
度
[i]+1){//注
以arr[j]结尾
j]<
从longest[j
最长递增子序
遍历在j之前
(j)的值。最
杂度为O(N^
(4)=2,L(5)=
下：
注意longest[
尾的序列的最长
]中找出最大值
序列
的所
后，
2)。
4。
j]<
长递
值
Sure之动态规划篇
解法3：O(NlgN）算法
假设存在一个序列d[1..9]={2，1，5，3，6，4，8，9，7}，可以看出来它的LIS长
度为5。
下面一步一步试着找出它。
我们定义一个序列B，然后令i=1to9逐个考察这个序列。
此外，我们用一个变量Len来记录现在最长算到多少了
首先，把d[1]有序地放到B里，令B[1]=2，就是说当只有1一个数字2的时候，长度为1
的LIS的最小末尾是2。这时Len=1
然后，把d[2]有序地放到B里，令B[1]=1，就是说长度为1的LIS的最小末尾是1，d[1]=2
已经没用了，很容易理解吧。这时Len=1
接着，d[3]=5，d[3]>B[1]，所以令B[1+1]=B[2]=d[3]=5，就是说长度为2的LIS的最小末
尾是5，很容易理解吧。这时候B[1..2]=1,5，Len＝2
再来，d[4]=3，它正好加在1,5之间，放在1的位置显然不合适，因为1小于3，长度为1
的LIS最小末尾应该是1，这样很容易推知，长度为2的LIS最小末尾是3，于是可以把5
淘汰掉，这时候B[1..2]=1,3，Len=2
继续，d[5]=6，它在3后面，因为B[2]=3,而6在3后面，于是很容易可以推知B[3]=6,
这时B[1..3]=1,3,6，还是很容易理解吧？Len=3了噢。
第6个,d[6]=4，你看它在3和6之间，于是我们就可以把6替换掉，得到B[3]=4。B[1..3]
=1,3,4，Len继续等于3
第7个,d[7]=8，它很大，比4大，嗯。于是B[4]=8。Len变成4了
第8个,d[8]=9，得到B[5]=9，嗯。Len继续增大，到5了。
最后一个,d[9]=7，它在B[3]=4和B[4]=8之间，所以我们知道，最新的B[4]=7，B[1..5]
=1,3,4,7,9，Len=5。
于是我们知道了LIS的长度为5。
注意
我们
义，
出L
然后
也就
法的
代码
Cpp代
意，这个1,3,
们就可以一个
但是如果后
IS的长度为
后应该发现一
就是说，我们
的时间复杂度
码如下（代码
代码
1.#include
2.#include
3.#include
4.
5.#define
6.intarra
7.intB[N]
文的解释
8.intlen;
9.
10.intLIS(
循环完一
11.intBiSe
12.
13.intmain
14.{
15.prin
16.
17.int
18.for(
19.{
20.
21.}
22.
23.retu
24.}
25.
26.intLIS(
27.{
28.len
29.B[0]
30.int
4,7,9不是L
个一个地插入
后面再出现两
为6。
一件事情了：
们可以使用二
度就降低到了
码中的数组B
N9//数组元
y[N]={2,
;//在动态规
//用于标示
intarray
遍后,B的长度
arch(int
()
tf("LIS:%d
i;
i=0;i
printf("B[%
rn0;
intarray
=1;
=array[0
i,pos=0
Sure
IS，它只是
入数据。虽然最
个数字8和
在B中插入
分查找，将每
O(NlogN)～
从位置0开
>
>
元素个数
1,6,3,5
规划中使用的数
示B数组中的元
,intn);/
度len即为所求
b,intlen,
\n",LIS(a
;++i)
d]=%d\n",
,intn)
];
;
之动态规
是存储的对应
最后一个d[9
和9，那么就
入数据是有序
每一个数字的
～！
开始存数据）
,4,8,7,
数组,用于记录
元素个数
/计算最长递增
求
intw);//
rray,N));
i,B[i]);
划篇
应长度LIS的
]=7更新进
就可以把8更
的，而且是进
的插入时间优
：
9};//原数组
录中间结果,其含
增子序列的长度
做了修改的二
最小末尾。
进去对于这组
更新到d[5],9
进行替换而不
优化到O(log
组
含义三言两语说
度,计算B数组
二分搜索算法
有了这个末尾
组数据没有什
更新到d[6]
不需要挪动—
N)~~~~~于
说不清,请参见
组的元素,arra
尾，
么意
，得
—
是算
见博
y[]
Sure之动态规划篇
31.
32.for(i=1;i
33.{
34.if(array[i]>B[len-1])//如果大于B中最大的元素，则直接插入到B数组末尾
35.{
36.B[len]=array[i];
37.++len;
38.}
39.else
40.{
41.pos=BiSearch(B,len,array[i]);//二分查找需要插入的位置
42.B[pos]=array[i];
43.}
44.}
45.
46.returnlen;
47.}
48.
49.//修改的二分查找算法，返回数组元素需要插入的位置。
50.intBiSearch(intb,intlen,intw)
51.{
52.intleft=0,right=len-1;
53.intmid;
54.while(left<=right)
55.{
56.mid=left+(right-left)/2;
57.if(b[mid]>w)
58.right=mid-1;
59.elseif(b[mid]
60.left=mid+1;
61.else//找到了该元素，则直接返回
62.returnmid;
63.}
64.returnleft;//数组b中不存在该元素，则返回该元素应该插入的位置
65.}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
