d.最长上升子序列
s.注意是严格递增
c.O(nlogn)
#include<iostream>
#include<stdio.h>
using namespace std; const int MAXN=;
int a[MAXN],b[MAXN];
//b[k]是序列a中所有长度为k的递增子序列中的最小结尾元素值
//用二分查找的方法找到一个位置，使得num>b[i-1]并且num<b[i]，并用num代替b[i]
int Search(int num,int low,int high){
int mid;
while(low<=high){
mid=(low+high)/;
if(num>=b[mid])low=mid+;
else high=mid-;
}
return low;
}
int DP(int n){
int i,len,pos;
b[]=a[];
len=;
for(i=;i<=n;i++){
if(a[i]>b[len]){//如果a[i]比b[]数组中最大还大直接插入到后面即可
len=len+;
b[len]=a[i];
}
else{//用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置
pos=Search(a[i],,len);
b[pos]=a[i];
}
}
return len;
} int main(){ int N;
int i; while(~scanf("%d",&N)){
for(i=;i<=N;++i){
scanf("%d",&a[i]);
} printf("%d\n",DP(N));
} return ;
}
c2.O(n^2)
#include<iostream>
#include<stdio.h>
using namespace std; #define MAXN 1005 int a[MAXN];
int dp[MAXN];//dp[i]表示以a[i]作为结尾的最长上升子序列的长度 int main(){ int N;
int i,j;
int temp;
int ans; while(~scanf("%d",&N)){ for(i=;i<=N;++i){
scanf("%d",&a[i]);
} dp[]=; for(i=;i<=N;++i){ temp=; for(j=;j<i;++j){
if(a[i]>a[j]){
if(temp<dp[j]){
temp=dp[j];
}
}
} dp[i]=temp+;
} ans=;
for(i=;i<=N;++i){
if(dp[i]>ans){
ans=dp[i];
}
} printf("%d\n",ans);
} return ;
}