牛客对应题目链接：最长上升子序列(二)_牛客题霸_牛客网 (nowcoder.com)
力扣对应题目链接：300. 最长递增子序列 - 力扣（LeetCode）
一、分析题目
1、贪心 + 二分
在考虑最长递增子序列的长度的时候，其实并不关心这个序列长什么样子，我们只是关心最后⼀个元素是谁。这样新来⼀个元素之后，我们就可以判断是否可以拼接到它的后面。
因此，我们可以创建⼀个数组，统计长度为 x 的递增子序列中，最后一个元素是谁。为了尽可能的让这个序列更长，我们仅需统计长度为 x 的所有递增序列中最后一个元素的最小值。统计的过程中发现，数组中的数呈现递增趋势，因此可以使用二分来查找插入位置。
2、动态规划
（1）dp[i] 的定义
表示 i 之前包括 i 的以 nums[i] 结尾的最长递增子序列的长度。
（2）状态转移方程
if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
（3）初始化
每一个 i 对应的 dp[i]（即最长递增子序列）起始大小至少都是 1。
（4）遍历顺序
从前往后遍历。
二、代码
1、贪心 + 二分（推荐）
//值得学习的代码 //O(NlogN) class Solution { int dp[100010] = { 0 }; // dp[i] 表⽰：⻓度为 i 的最⼩末尾 int pos = 0; public: int LIS(vector<int>& a) { for(auto x : a) { // 查找 x 应该放在哪个位置 if(pos == 0 || x > dp[pos]) { dp[++pos] = x; } else { // ⼆分查找插⼊位置 int l = 1, r = pos; while(l < r) { int mid = (l + r) / 2; if(dp[mid] >= x) r = mid; else l = mid + 1; } dp[l] = x; } } return pos; } };
2、动态规划
//力扣AC代码 //从前往后遍历（推荐） class Solution { public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); if(n<=1) return n; vector<int> dp(n, 1); int res=0; for(int i=1; i<n; i++) { for(int j=0; j<i; j++) { if(nums[j]<nums[i]) dp[i]=max(dp[i], dp[j]+1); } if(dp[i]>res) res=dp[i]; } return res; } }; //从后往前遍历 class Solution { public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); vector<int> dp(n, 1); int res=0; for(int i=n-1; i>=0; i--) { for(int j=i+1; j<n; j++) { if(nums[i]<nums[j]) dp[i]=max(dp[i], dp[j]+1); } res=max(res, dp[i]); } return res; } }; //记忆化搜索 class Solution { public: int dfs(int pos, vector<int>& nums, vector<int>& memo) { if(memo[pos]!=0) return memo[pos]; int ans=1; for(int i=pos+1; i<nums.size(); i++) { if(nums[i]>nums[pos]) ans=max(ans, dfs(i, nums, memo)+1); } memo[pos]=ans; return ans; } int lengthOfLIS(vector<int>& nums) { int n=nums.size(); vector<int> memo(n); int res=0; for(int i=0; i<n; i++) res=max(res, dfs(i, nums, memo)); return res; } };
三、反思与改进
这道题我是想用动态规划来做的，但也没做出来，不过这里用不了动态规划，会超时，如果数据量小的话可以使用。贪心 + 二分这种思路没想到，但这种解法才比较具有普遍性，不需要过多考虑数据量的问题（感觉这种题得多做几次才会有思路）。
