定义：
设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)
例如3，18，7，14，10，12，23，41，16，24。
若存在i1<i2<i3< … < ie （1<=i<=n）且有a(i1)<a(i2)< … <a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。---- 百度百科
递归代码core：
递归代码core：
1 int f(int i){ 2 if(i==1) return 1;//递归边界 3 if(a[i]>=a[i-1]) return f(i-1)+1;//选，长度++ 4 else return f(i-1); //不选保持原来长度 5 }
记忆化搜索代码core:（需要再研究）
1 int f(int i){ 2 if(i==1) return 0; 3 if(dp[i]!=0) return dp[n];//记忆化 4 if(a[i]>=a[i-1]) return dp[i]=f(i-1)+1; 5 else return dp[i]=f(i-1); 6 }
dp代码core：
1 for(int i=1;i<=n;i++){ 2 cin>>a[i]; 3 dp[i]=1; 4 } 5 dp[0]=-1; 6 for(int i=1;i<=n;i++){ 7 for(int j=1;j<i;j++){ 8 if(a[i]>=a[j]) dp[i]=max(dp[i],dp[j]+1); 9 } 10 ans=max(ans,dp[i]); 11 } 12 cout<<ans;
单调序列二分优化代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #define N 10001 5 using namespace std; 6 int a[N],b[N]; 7 int n; 8 inline int read(){ 9 char ch=getchar(); 10 int f=1,x=0; 11 while(ch<'0'||ch>'9'){ 12 if(ch=='-') f=-1; 13 ch=getchar(); 14 } 15 while(ch>='0'&&ch<='9'){ 16 x=(x<<1)+(x<<3)+ch-'0'; 17 ch=getchar(); 18 } 19 return f*x; 20 } 21 int main(){ 22 n=read();//快读 23 for(int i=1;i<=n;i++){ 24 a[i]=read(); 25 } 26 b[1]=a[1]; 27 int len=1;//初始化 28 for(int i=2;i<=n;i++){ 29 if(a[i]>=b[len]){ 30 b[++len]=a[i];//如果可以接上就给他接上 31 } 32 else{//替换掉 33 int j=upper_bound(b+1,b+1+len,a[i])-b;//找到第一个比B大的数的下标 34 b[j]=a[i]; 35 } 36 } 37 printf("%d",len); 38 return 0; 39 }
1.当你看不懂的时候一定要拿出例子来模拟一下代码！