题目链接：
线性DP代码（O(n^2)时间复杂度）：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;int n = 0;
int arr[N];
int dp[N];
vector<int> q;signed main(){int x;while(cin >> x) arr[++n] = x;//找到最大不上升序列for(int i = 1; i <= n; i++){dp[i] = 1;for(int j = 1; j < i; j++){if(arr[j] >= arr[i]){dp[i] = max(dp[i], dp[j]+1);}}}int ans = 0;for(int i = 1; i <= n; i++) ans = max(ans, dp[i]);//找到需要几套系统q.push_back(50010);for(int i = 1; i<= n; i++){bool check = false;for(int j = 0; j < q.size();j++){if(q[j] >= arr[i]){q[j] = arr[i];check = true;break;}}if(!check) q.push_back(arr[i]);}cout << ans << endl << q.size() << endl;return 0;
}贪心+二分思路优化：
①题目要求我们求出最长不上升子序列，当序列每个数字都选择当前最大的时候（符合不上升规则），那么得出的序列就是最长的不上升子序列。
②我们用 g[i] 数组来记录长度为i的子序列结尾最后一个数字是谁。g[]数组记录的是最长不上升子序列长度，不记录最长不上升子序列的具体数字。枚举数组 arr[] ，当 arr[i] <= g[i]的时候，将arr[i] 添加到g[i+1]中；当 arr[i] > g[i]，要在 g[] 数组中找到最后一个大于 arr[i] 的数字，更新 g[r] 的最大值为 arr[i]。
③这道题是求的是降序的最长子序列，容易搞错二分条件。要明白 g[] 数组的含义。
贪心+二分代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;int arr[N]; //存数据
//len为g[]的长度， g[i]存的是长度为i序列，最后一个字母是谁?
//g[]数组不存最长不上升子序列，记录的是长度
int len = 1, g[N], p;signed main(){//读入数据int k;while(cin >> k) arr[++p] = k;//对g初始化g[1] = arr[1];for(int i = 2; i <= p; i++){if(g[len] >= arr[i]){g[++len] = arr[i];}else{//在有序数组g[]中查找最后一个大于arr[i]的数字 返回rint l = 0, r = len+1;while(l+1 < r){int mid = (l+r) / 2;if(g[mid] >= arr[i]){l = mid;}else r = mid;}g[r] = arr[i];}}//找到需要几套系统vector<int> q; q.push_back(arr[1]);for(int i = 2; i <= p; i++){int check = false;for(int j = 0; j < (int)q.size(); j++){if(q[j] >= arr[i]){q[j] = arr[i];check = true;break;}}if(!check){q.push_back(arr[i]);}}cout << len << endl << q.size() << endl;return 0;
}