复杂度均为 O(nlogn)
长度查找：
/*最长非降子序列*/ int n; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); if (n==0) //0个元素特判一下 { printf("0\n"); return 0; } d[1]=a[1]; //初始化 int len=1; for (int i=2;i<=n;i++) { if (a[i]>=d[len]) d[++len]=a[i]; //如果可以接在len后面就接上 // 上升:a[i]>d[len] else //否则就找一个最该替换的替换掉 { int j=upper_bound(d+1,d+len+1,a[i])-d; //找到第一个大于它的d的下标 // 上升:用lower_bound d[j]=a[i]; } } printf("%d\n",len);序列记录：
/*最长非降子序列*/ int d[100], c[100], a[100], len = 1; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++ i) { scanf("%d", &a[i]); } d[1] = a[1], c[1] = 1; for (int i = 2; i <= n; ++ i) { if (d[len] <= a[i]) { d[++ len] = a[i], c[i] = len; } else { int j = upper_bound(d + 1, d + len + 1, a[i]) - d; d[j] = a[i], c[i] = j; } } stack<int> sta; for (int i = n, j = len; i >= 1; -- i) { if (c[i] == j) { sta.push(a[i]); --j; } if (j == 0) break; } printf("%d\n", len); while (!sta.empty()) { printf("%d ", sta.top()); sta.pop(); } return 0; }参考：最长不下降子序列详解（一）
