问题描述
300.最长递增子序列 本题简写为LIS问题，与LCS问题（最长公共子序列）相对。
解题思路
动态规划
关键在于，dp[i]表示什么含义便于解这道题，子序列不一定连续，所以为了便于求解，dp[i]应该表示为以nums[i - 1]结尾的最长严格递增子序列的长度；
递推关系为:
if (nums[i - 1] > nums[j - 1]) // j < i，表示nums[i - 1]前的任意一个元素
dp[i] = max(dp[j] + 1, dp[i])
贪心
动态规划的时间复杂度为$O(n^2)$，这里存在一个时间复杂度更低的贪心解法：
动态规划的时间$O(n^2)$的时间复杂度中，$O(n)$的时间复杂度在与遍历整个数组，这是无法避免的；剩下的$O(n)$的时间复杂度，实际上在找一个满足j < i以及nums[j] < nums[i]的并且使dp[j]最大的j；
那么，可以转化为找dp[j]固定的情况下，最小的一个nums[j]，这样必然能够优先满足，nums[i] > nums[j]；因此我们构造一个贪心数组：min_len，min_len[i] = x表示长度为i的上升子序列的最小结尾元素为x。考虑到min_len一定是个单调递增的数组（易证），那么我们可以基于这个单调递增的特性，利用二分查找，找到满足min_len[j] < nums[i]的最大的j，即利用$O(\log n)$找到最佳转移位置。
代码
动态规划
class Solution {
public:
int lengthOfLIS(vector<int> &nums) {
vector<int> dp(nums.size() + 1, 1); // dp[0]不考虑，至少有一个元素，所以初始化为1
// dp[1] = 1;
// int index = 0;
int m = 0;
for (int i = 1; i <= nums.size(); i++) {
for (int j = 1; j < i; j++) {
if (nums[i - 1] > nums[j - 1])
dp[i] = max(dp[j] + 1, dp[i]);
}
if (dp[i] > m)
m = dp[i];
}
return m;
}
};
贪心+二分
class Solution {
public:
int GetIdx(vector<int> &min_len_tail, int len, int target) {
int left = 1, right = len;
int mid = left + (right - left) / 2;
while (left < right) {
if (min_len_tail[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
mid = left + (right - left) / 2;
}
return left;
}
int lengthOfLIS(vector<int>& nums) {
// 贪心，要让序列上升得尽可能慢
// 先找到第一个波谷
int n = nums.size();
vector<int> min_len_tail(n + 1, nums[0]); //min_len_tail[i]表示长度为i的上升子序列的末尾元素的最小值
int len = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > min_len_tail[len]) {
min_len_tail[++len] = nums[i];
} else {
int idx = GetIdx(min_len_tail, len, nums[i]);
min_len_tail[idx] = nums[i];
}
}
return len;
}
};