最长上升子序列的的相关定义、解释参考这篇博客，写的真的很棒：传送门
用里边的话来说，就是你把数据拆分成N组数据，如果是第一组，我总能在后面的组中找到一个P大于第一组的所有数据。以此类推，不管你多少组，我总能在它的下一组数据中找到一个比它大的。要是这个N最小，其实这个N就是最长上升子序列！
最长上升子序列有两种解法：
第一种：复杂度O(n^2)，有时候会超时，比较少用，一搬都是都是用O(logn * n)的解法，这个解法我都有点生疏了
nums数组就是初始的数组！
递推公式：num[i] = *max_element(num , num + i) +1 ;
第一个for循环：走nums数组，记录当前到达的位置！
第二个for循环：再走一遍num数组，找到最大的，然后+1
int lengthOfLIS(vector<int>& nums) { if(nums.size()==0) return 0; vector<int> num; for(int i = 0 ; i < nums.size() ; i++){ int text = 1 ; for(int j = 0 ; j < i ; j++){ if(nums[j] < nums[i]){ text = max(text,num[j]+1); } } num.push_back(text); } int len = num.size(); return *max_element(num.begin(),num.end()); // 返回num数组中最大的数，也就是最长的上升子序列 }
第二种：运用二分，构造一个pos数组，用来存储当前长度下的最长递增子序列的长度
注意：这里的pos数是有序的，从小到大！
所以可以用二分查找
#include<bits/stdc++.h> using namespace std; int main() { int a ; cin>>a; int nums[50005]; for(int i = 0; i < a ; i++) cin>>nums[i]; int pos[50005]; int k = 0; pos[k++] = nums[0]; /// 把第一个装进去 for(int i = 1 ; i < a ; i++){ if(nums[i] > pos[k-1]) // 如果大于pos数组最末尾的哪一个数，就直接装进去 pos[k++] = nums[i]; else{/// 否则是用一个二分查找，找到第一个大于等于的数，然后用nums[i]替换掉,这样子就是再维护一个最长的上升序了 int len = lower_bound(pos,pos+k, nums[i])-pos; pos[len] = nums[i]; } } cout<<k<<endl; return 0; }
多刷点题就理解 了
例题1：https://ac.nowcoder.com/acm/contest/911/G
例题2：https://ac.nowcoder.com/acm/contest/5733/M（变形，题目还是不错的）
例题3：https://leetcode-cn.com/problems/longest-increasing-subsequence/（模板题）
例题4：http://acm.hdu.edu.cn/showproblem.php?pid=5489（变形，挺不错的）
一类的题：
例题5：http://acm.hdu.edu.cn/showproblem.php?pid=1257（模板题）
例题6：https://pintia.cn/problem-sets/994805046380707840/problems/994805063166312448