求解最长递增子序列长度|动态规划+二分查找:C\C++实现

简介:
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 }
目录
相关文章
|
2月前
|
算法 JavaScript Java
【状态压缩】【动态规划】【C++算法】1125.最小的必要团队
【状态压缩】【动态规划】【C++算法】1125.最小的必要团队
|
1月前
|
算法 C++
【动态规划】斐波那契数列模型(C++)
【动态规划】斐波那契数列模型(C++)
|
1月前
|
算法 C++
【动态规划】零基础解决路径问题(C++)
【动态规划】零基础解决路径问题(C++)
|
2月前
|
算法 测试技术 Serverless
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
|
2月前
|
Go C++
【力扣】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
【2月更文挑战第17天】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
36 8
|
2月前
|
存储 并行计算 算法
C++动态规划的全面解析:从原理到实践
C++动态规划的全面解析:从原理到实践
113 0
|
2月前
|
编解码 算法 程序员
【C++ 泛型编程 高级篇】 C++ 14 模版元编程 遍历元组 编译期生成整数序列 std::index_sequence和std::make_index_sequence 使用指南(三)
【C++ 泛型编程 高级篇】 C++ 14 模版元编程 遍历元组 编译期生成整数序列 std::index_sequence和std::make_index_sequence 使用指南
41 0
|
2月前
|
C++ 索引
【C++ 泛型编程 高级篇】 C++ 14 模版元编程 遍历元组 编译期生成整数序列 std::index_sequence和std::make_index_sequence 使用指南(二)
【C++ 泛型编程 高级篇】 C++ 14 模版元编程 遍历元组 编译期生成整数序列 std::index_sequence和std::make_index_sequence 使用指南
99 0
|
2月前
|
存储 编译器 程序员
【C++ 泛型编程 高级篇】 C++ 14 模版元编程 遍历元组 编译期生成整数序列 std::index_sequence和std::make_index_sequence 使用指南(一)
【C++ 泛型编程 高级篇】 C++ 14 模版元编程 遍历元组 编译期生成整数序列 std::index_sequence和std::make_index_sequence 使用指南
112 0
|
1天前
|
C++
什么是析构函数,它在C++类中起什么作用
什么是析构函数,它在C++类中起什么作用?
19 11