最长递增子序列两种算法实现（动态规划，二分查找）

恭喜你刷到博主 DP 经典题目详解部分第一期，想学好 DP 请关注订阅，会持续更新！！！！！

建议先阅读DP算法入门

00001 最长递增子序列（Longest Increasing Subsequence，简写 LIS）

提要：本文介绍两种算法实现

一种是动态规划（算法复杂度 O（n ^ 2））：

通过本题了解设计动态规划的通用技巧 ————> 数学归纳思想

一种是二分查找（算法复杂度 O（n log n））：

由 patience game 的纸牌游戏（甚至有一种排序方法就叫做 patience sorting（耐心排序））的思想衍生的算法

---

01 动态规划

假设这个结论在 k < n 时成立，然后想办法证明 k = n 的时候此结论也成立。如果能够证明出来，那么就说明这个结论对于 k 等于任何数都成立类似的，我们设计动态规划算法，不是需要一个 dp 数组吗？我们可以假设 dp[0...i - 1] 都已经被算出来了，怎么通过这些结果算出 dp[i]？

首先要定义清楚 dp 数组的含义，即 dp[i] 的值到底代表着什么？

我们的定义是这样的：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度

重申一遍 DP 框架

明确状态 -> 定义 dp 数组/函数的含义 -> 明确选择-> 明确 base case

int lengthOfLIS(vector<int> &nums)
{if (nums.empty())return 0;int n = nums.size();//dp 数组应该全部初始化为 1，因为子序列最少也要包含自己，所以长度最小为 1vector<int> dp(n, 1); // 填充 dp 数组for (int i = 1; i < n; ++i){//找到前面那些结尾比 i 小的子序列，然后把 i 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加 1for (int j = 0; j < i; ++j){if (nums[i] > nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}}// 寻找 dp 数组中的最大值即找最长递增子序列int res = 0;for (int i = 0; i < n; ++i){res = max(res, dp[i]);}return res;
}

10 二分查找

首先我们玩下叫 patience game 的纸牌游戏

规则：他的实现原理就是首先使用数组中的第一个数字创建一个纸牌堆，然后逐个读取数组中的剩余数字，如果当前数字比所有纸牌堆中最上面的数字都大，就新建一个纸牌堆，把当前数字放到该堆中。否则找到一个最上面数字不小于当前数字的纸牌堆，把当前数字放到该纸牌堆中

---

我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗？牌堆顶的牌不是有序吗？

———> 用到二分查找了：搜索当前牌应放置的位置

---

int LIS(vector<int> &nums)
{if (nums.empty())return 0;vector<int> top; // 用于存储牌堆的顶端元素for (int poker : nums){// 二分查找，找到比 poker 大的最小位置auto it = lower_bound(top.begin(), top.end(), poker);// 如果没有找到合适的位置，说明 poker 应该作为新的牌堆加入if (it == top.end()){top.push_back(poker);}else{// 否则，更新找到的位置*it = poker;}}// 牌堆数即为 LIS 长度return top.size();
}

---

这里的二分查找直接用了 STL 算法库中的 lower_bound （因为lower_bound 底层实现使用二分查找）

想要了解二分查找的实现的参考

template <typename ForwardIterator, typename T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val) {while (first < last) {ForwardIterator mid = first + (last - first) / 2;  // 计算中点if (*mid < val) {first = mid + 1;  // 如果 mid 小于 val，则搜索右半部分} else {last = mid;  // 如果 mid 大于或等于 val，则搜索左半部分}}return first;  // 返回第一个不小于 val 的元素
}

---