题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
思路
要找到一个数组中最长严格递增子序列的长度，可以使用动态规划来解决这个问题。
我们再来介绍以下动态规划：
动态规划（Dynamic Programming，简称DP）是一种常见的解决问题的算法思想，通常用于求解具有重叠子问题和最优子结构性质的问题。动态规划算法通过将原问题分解为相对简单的子问题，并保存子问题的解，从而避免重复计算，提高了算法的效率。
动态规划算法通常适用于具有以下两个特点的问题：
- 最优子结构：问题的最优解可以通过子问题的最优解来求解。
- 重叠子问题：问题的计算过程中包含重复的子问题。
在动态规划算法中，一般采用自底向上或自顶向下的方式来解决问题。下面是动态规划算法的一般步骤：
- 确定状态：找到子问题的描述，定义状态表示问题的解。
- 确定状态转移方程：找到子问题之间的递推关系，即如何通过子问题的解来求解原问题的解。
- 边界条件：确定边界条件，即最小的子问题的解。
- 计算顺序：确定问题的计算顺序，一般可以采用自底向上或自顶向下的方式进行计算。
- 实现算法：根据以上步骤实现动态规划算法。
动态规划算法的核心思想是将原始问题分解成相对简单的子问题，并通过保存子问题的解避免重复计算，从而提高算法的效率。它在很多实际问题中都有广泛的应用，如最短路径问题、背包问题、字符串匹配等。
本题的动态规划解法如下：
- 创建一个与原始数组大小相同的dp数组，dp[i]表示以nums[i]结尾的最长递增子序列的长度。
- 初始化dp数组的每个元素为1，因为每个单独的元素本身就构成一个长度为1的递增子序列。
- 遍历数组，对于每个位置i，再遍历其之前的所有位置j（0 <= j < i），如果nums[i]大于nums[j]，说明可以将nums[i]接在以nums[j]结尾的递增子序列后面形成更长的递增子序列，即更新dp[i] = max(dp[i], dp[j] + 1)。
- 最终找到dp数组中的最大值，即为最长严格递增子序列的长度。
Code
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int maxLength = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLength = max(maxLength, dp[i]);
}
return maxLength;
}
这样，通过动态规划算法，可以高效地找到给定数组中最长严格递增子序列的长度。
但是考虑到通过DP解的话时间复杂度为O(n*n)，时间复杂度比较高。
因此我们可以通过贪心+二分查找的解法降低时间复杂度。
力扣官方题解如下：
Code
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int len = 1, n = (int)nums.size();
if (n == 0) {
return 0;
}
vector<int> d(n + 1, 0);
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) {
d[++len] = nums[i];
} else {
int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return len;
}
};
