# 300.最长递增子序列

## 问题描述
[300.最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/)
本题简写为LIS问题，与LCS问题（最长公共子序列）相对。

## 解题思路
### 动态规划
关键在于，`dp[i]`表示什么含义便于解这道题，子序列不一定连续，所以为了便于求解，`dp[i]`应该表示为以`nums[i - 1]`结尾的最长严格递增子序列的长度；

递推关系为:
```cpp
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)$找到最佳转移位置。

## 代码
### 动态规划
```cpp
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;
    }
};
```

### 贪心+二分
```cpp
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;
    }
};
```