最长上升子序列（O^n^2）算法
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <iomanip> #include <cmath> #include <ctime> #include <map> #include <set> using namespace std; #define lowbit(x) (x&(-x)) #define max(x,y) (x>y?x:y) #define min(x,y) (x<y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.141592653589793238462 #define INF 0x3f3f3f3f3f #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; int a[100006],dp[100006],n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); int maxn=-1; for(int i=1;i<=n;i++) { dp[i]=1; for(int j=1;j<=i;j++) { if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1); } maxn=max(maxn,dp[i]); } printf("%d ",maxn); return 0; }
(Onlogn)算法
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <iomanip> #include <cmath> #include <ctime> #include <map> #include <set> using namespace std; #define lowbit(x) (x&(-x)) #define max(x,y) (x>y?x:y) #define min(x,y) (x<y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.141592653589793238462 #define INF 0x3f3f3f3f3f #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; int x,dp[100006],n; int main() { scanf("%d",&n); int top=0; dp[0]=-1; for(int i=0;i<) for(int i=0;i<n;i++) { scanf("%d",&x); if(x>dp[top]) dp[++top]=x; else//替换更新 { int l=1,r=top; while(l<=r) { int mid=(l+r)>>1; if(x>dp[mid]) l=mid+1; else r=mid-1; } dp[l]=x; } } }