01
|
/*
求解最长递增子序列长度 */
|
02
|
#include
<iostream>
|
03
|
#include
<limits>
|
04
|
05
|
using namespace std;
|
06
|
07
|
//int
x[] = {1,-1,2,-3,4,-5,6,-7};
|
08
|
int x[]
= {2, 1, 5, 3, 6, 4, 8, 9, 7};
|
09
|
int disp_array(int a[], int len);
|
10
|
int find_first_bigger(int a[], int last, int key);
|
11
|
12
|
int main()
|
13
|
{
|
14
|
int len
= sizeof(x)/sizeof(x[0]);
|
15
|
int *z
= new int(len
+ 1);
|
16
|
/*
z[i] = min(t|t:长度为i的子序列的最后一个元素) */
|
17
|
z[0]
= std::numeric_limits<int>::min();
|
18
|
for (int i
= 1; i <= len; ++i)
|
19
|
{
|
20
|
z[i]
= 0;
|
21
|
}
|
22
|
23
|
disp_array(x,
len);
|
24
|
disp_array(z,
len + 1);
|
25
|
26
|
int t,
lislen = 0;
|
27
|
for (int i
= 0; i < len; ++i)
|
28
|
{
|
29
|
t
= find_first_bigger(z, lislen, x[i]);
|
30
|
if (t
> lislen)
|
31
|
z[++lislen]
= x[i]; /*
z[]中没有比x[i]大的*/
|
32
|
else
|
33
|
z[t]
= x[i]; /*
z[t]第一个比x[i] */
|
34
|
35
|
}
|
36
|
37
|
disp_array(z,
len + 1);
|
38
|
cout
<< "LIS
= " <<
lislen << endl;
|
39
|
|
40
|
return 0;
|
41
|
}
|
42
|
43
|
/**
|
44
|
*
@brief 在数组a[0..last]中，自左向又查找第一个比key大的数的下标
|
45
|
*
时间复杂度O(lg(n))
|
46
|
*
|
47
|
*
@param a[]
|
48
|
*
@param last
|
49
|
*
@param key
|
50
|
*
|
51
|
*
@return 返回下标，如果没有比key大的则返回last+1
|
52
|
*/
|
53
|
int find_first_bigger(int a[], int last, int key)
|
54
|
{
|
55
|
int m,
p = -1, q = last + 1;
|
56
|
/*
assume: a[-1] < key <= a[last + 1] */
|
57
|
while (p
+ 1 != q)
|
58
|
{
|
59
|
/*
invartant: 0 <= p + 1 < q <= last + 1 && a[p] < key <= a[q]*/
|
60
|
m
= p + ((q - p)>>1);
|
61
|
if (a[m]
< key)
|
62
|
p
= m;
|
63
|
else
|
64
|
q
= m;
|
65
|
}
|
66
|
67
|
return q;
|
68
|
}
|
69
|
70
|
int disp_array(int a[], int len)
|
71
|
{
|
72
|
for (int i
= 0; i < len; ++i)
|
73
|
{
|
74
|
cout
<< a[i];
|
75
|
if (i
== len -1)
|
76
|
cout
<< endl;
|
77
|
else
|
78
|
cout
<< "
";
|
79
|
}
|
80
|
|
81
|
}
|