題意：給出一個序列，求它的最長上升子序列的長度
題目鏈接：https://ac.nowcoder.com/acm/problem/26156
輸入:n代表長度，然后是一個字符串
分析：用dp[i]表示長度為i+1的上升子序列末尾元素的最小值（一開始初始化為INF）
容易想到的做法是兩個循環，第一個循環對長度i做循環，然后第二層循環對j，對于每個aj，如果i=0(也就是長度為1),或者dp[i-1]<aj時，就有dp[i]=min(dp[i],aj),這種做法的時間復雜是O(N^2)
但是dp數組除了INF，其它都是單調遞增的，所以我們可以用lower_bound()函數進行優化
lower_bound()函數是返回大于等于val的第一個元素位置，返回的是一個指針
具體過程可看代碼
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f;//這個數是1e9數量級的，且可以用memset函數 const int maxn=5e4+7; const double pi=acos(-1); const int mod=1e9+7; int dp[maxn],a[maxn]; inline ll read(){ll x=0,tmp=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') tmp=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return tmp*x; }int main(){int n;cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}fill(dp,dp+maxn,inf);for(int i=1;i<=n;i++){*lower_bound(dp,dp+n,a[i])=a[i];}cout<<lower_bound(dp,dp+n,inf)-dp<<endl;return 0; }
?
)
)
