默认是单调递增：
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; int a[1000005]; char c[1000005]; int maxv[1000005]; int bin(int x,int len) { int left,right,mid; left=1; right=len; while(left<=right) { mid=left+(right-left)/2; if(maxv[mid]==x) return mid;//(2)return mid+1;//非递减 else if(maxv[mid]<x)//(1)maxv[mid]>x:单调递减 left=mid+1; else right=mid-1; } return left; } int main() { int n,i,j,len; scanf("%d",&n); while(n--) { scanf("%s",c); for(i=0; i<strlen(c); i++) { a[i+1]=c[i]-'a'; } maxv[1]=a[1]; len=1; for(i=2; i<=strlen(c); i++) { if(a[i]>maxv[len])//(1) < maxv[++len]=a[i]; else { int pos=bin(a[i],len); maxv[pos]=a[i]; } } printf("%d\n",len); } }