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 |
} |
