题意： 求所给出长度为 N 的最长上升子序列长度 ""思路：**
(1) \(O(n^2)\)的 动态转移： 设\(dp[i]\)表示以\(i\)结尾的最长单调子序列，那么当\(arr[i]>arr[j]时\) \(dp[i]=max(dp[j]+1,dp[i]) (j\in[1,i))\)
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(0); cin.tie(0); #define accept 0 #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int inf = 0x3f3f3f3f; const int maxn = 1e3+7; const int maxm = 1e6+7; const int mod = 1e9+7; int dp[maxn]; int arr[maxn]; int main(){ int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ scanf("%d",&arr[i]); dp[i] = 1; } int ans = -1; for(int i=1;i<=n;i++){ for(int j=1;j<i;j++){ if(arr[i]>arr[j]) dp[i] = max(dp[j]+1,dp[i]); } ans = max(ans,dp[i]); } printf("%d\n",ans); } return accept; }(2) \(O(n^2)\)\(d[i] = 长度为i+1\)的递增子序列中末尾的最小值(不存在就是INF) 最开始用INF初始化dp数组的值，然后从前往后考虑数列的元素，对于每个\(a_j\)，如果\(i\) 处于第一个位置 或者\(a[j] >= a[i]，\)使得\(a[j] = a[i]\)并且\(break\)，最后第一个dp数组中值为INF的下标即为结果 实际上很类似单调栈，将数组依次后移，如果遇到比前面dp小的就将其放在dp第一个比该值大的前一位（实现单调栈类似的效果），但是长度仍然按照最长计算。 因为要使得子序列最长，从贪心的角度来想如果该序列足够长，我们尽量使每个递增的差值最小，这样就能排更多的值。
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(0); cin.tie(0); #define accept 0 #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int inf = 0x3f3f3f3f; const int maxn = 1e3+7; const int maxm = 1e6+7; const int mod = 1e9+7; int n; int arr[maxn]; int dp[maxn]; int main() { int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ scanf("%d",&arr[i]); } for(int i=1;i<=maxn;i++){ dp[i] = inf; } dp[0] = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i == 1|| dp[j] >= arr[i]) { dp[j] = arr[i]; break; } } } int ans = 0; while(dp[ans] != inf) ans++; printf("%d\n", ans-1); } return 0; }(3)\(O(nlogn)\) 从第二种方法就能看出来，对于查找部分，我们不必要再遍历比较，可以使用二分进行优化
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(0); cin.tie(0); #define accept 0 #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int inf = 0x3f3f3f3f; const int maxn = 1e3+7; const int maxm = 1e6+7; const int mod = 1e9+7; int n; int arr[maxn]; int dp[maxn]; int main() { int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ scanf("%d",&arr[i]); dp[i] = inf; } dp[0] = 0; for(int i = 1; i <= n; i++) { *lower_bound(dp+1,dp+n+1,arr[i]) = arr[i]; } int ans = lower_bound(dp+1,dp+1+n,inf) - dp; printf("%d\n", ans-1); } return 0; }转载于:https://www.cnblogs.com/Tianwell/p/11415894.html
