c++最长上升子序列长度
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000
//最长上升子序列
//方法1：（时间复杂度 O（N^2））
//dp[i]:以位置i为结尾的最长递增子序列的长度
int dp[maxn];
int arr[maxn];
int ans=1;
void solve1(int n){
for(int i=0;i<n;i++) dp[i]=1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(arr[i]>arr[j]){
dp[i]=max(dp[i],1+dp[j]);
if(dp[i]>ans) ans=dp[i];
}
}
}
cout<<"ans = "<<ans<<endl;
}
//方法2：时间复杂度O（N*log N）
//end[i]:长度为i+1子序列的最小结尾
int endss[maxn];
int len=0;//len为end数组的实际大小，也是答案所在
//bs函数：用来搜索endss数组中比arr[i]小(不能相等)的第一个元素下标（从右往左算的话）
//举个例子：现在arr[i]==7
//endss[3 6 8 ]
//下标 0 1 2 len
//bs就是要找6的下标（大小最接近 arr[i]且比 arr[i] 小）
//而因为endss数组本质上具有单调性的，所以用二分搜索
int bs(int num){
if(endss[0]>=num) return -1;
int l=0,r=len-1;
while(l<=r){
int m=(l+r)/2;
if(endss[m]>=num){
r=m-1;
}else{
l=m+1;
}
}
return l-1;
}
void solve2(int n){
endss[0]=arr[0];
len++;
for(int i=1;i<n;i++){
if(arr[i]>endss[len-1]){
endss[len++]=arr[i];
}else{
int find=bs(arr[i]);
if(find != -1){
endss[++find]=arr[i];
}else{
endss[0]=arr[i];
}
}
}
cout<<"len = "<<len<<endl;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>arr[i];
solve1(n);
solve2(n);
return 0;
}