题目：最长递增子序列
解法一：动态规划
状态定义：dp[ i ]指的是“以第 i 个元素结尾的子序列的最大长度”
状态转移：dp[ i ] = max( dp[ i ], dp[ j ] + 1 )，其中 j 是不大于 i 的正整数；
方程的意义是——假设正在处理 nums[i]，我们想把它接在一个现有的子序列后面。
为了保证“严格递增”，必须满足两个条件：
1. **位置在前后**：那个数必须在 i 之前（即 j < i）。
2. **数值从小到大**：那个数必须比 `nums[i]` 小（即 nums[j] < nums[i]）。
1int lengthOfLIS(vector<int>& nums)
2{
3 if(nums.empty()) return 0;
4 std::vector<int> dp(nums.size(), 1);
5 int res = 1;
6 for(int i = 0; i < nums.size(); i++)
7 {
8 for(int j = 0; j < i; j++)
9 {
10 if(nums[j] < nums[i])
11 {
12 dp[i] = std::max(dp[i], dp[j] + 1);
13 }
14 }
15 res = std::max(res, dp[i]);
16 }
17 return res;
18}
补充解法：二分查找维护最小末尾
维护一个数组 dp，dp【i】的含义是：长度为 i + 1 的子数组的末尾元素的最小值
然后遍历数组 nums，在 dp 中通过二分查找，看看 num 的位置在哪里
- 如果不存在任何一个数大于等于 num，也就是 it = num.end（），就将 num 接入 dp 的末尾，意味着子序列的长度可以加一
- 如果当前数组中已经有一个数大于等于 num 了，就将这个数替换为 num（降低末尾元素的值，确保后续可以有更多元素加入）
1int lengthOfLIS(vector<int>& nums)
2{
3 std::vector<int> dp;
4
5 for(int num : nums)
6 {
7 auto it = std::lower_bound(dp.begin(), dp.end(), num);
8 if(it == dp.end())
9 {
10 dp.push_back(num);
11 }
12 else
13 {
14 *it = num;
15 }
16 }
17 return dp.size();
18}
来源：语雀原笔记
补充解法：原地修改
1int lengthOfLIS(vector<int>& nums)
2{
3 // 从第一个元素开始
4 auto end = nums.begin();
5
6 for(int num : nums)
7 {
8 // 在区间内找到第一个大于等于 num 的位置
9 auto it = lower_bound(nums.begin(), end, num);
10
11 // 将原来 g[j] 的值（一个较大的数）替换成更小的 num
12 // 为什么直接认为 num 一定小于之前的末尾元素？
13 /* 因为 lower_bound(first, last, x) 返回的是第一个满足 元素 >= x 的位置。
14 因此，当 it != end 时，*it >= x 恒成立。
15 于是执行 *it = x 后：
16 如果 *it > x，新值变小（这正是我们想要的，因为要降低该长度的最小末尾）。
17 如果 *it == x，新值不变（没有影响）。
18 没有可能出现 *it < x 的情况，所以不存在“当前元素大于原末尾”的问题*/
19 *it = num;
20
21 if(it == end)
22 {
23 // 此时将长度加一
24 end++;
25 }
26 }
27 return end - nums.begin();
28}
来源：语雀原笔记