最长上升子序列（LIS）的nlogn算法。
用dp[i]来表示长度为i的LIS末尾数字的最小值。每输入一个数，，就把它插到dp数组合适的位置，而dp[]一定是有序的（因为每一步更新的保证），因此可以二分，用logn的复杂度就可以完成插入（准确地说是更新）。这个链接里讲得比较清楚：?1587
#include <iostream>#include <string.h>#include <stdio.h>using namespace std;int getPos(int dp[], int l, int r, int key){if(key >= dp[r]) return r + 1;int m;while(l < r){m = (l + r) / 2;if(dp[m] <= key) l = m + 1;else r = m;}return l;}int main(){int t;scanf("%d", &t);while(t–){int a[40005];int n, dp[40005], len = 0;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &a[i]);int pos = getPos(dp, 0, len, a[i]);//二分找合适的位置dp[pos] = a[i];//插到末尾（更新）if(pos > len) len = pos;//更新长度}printf("%d\n", len);}return 0;}
摘抄美文4、承诺是一件美好的事情，但美好的东西往往不会变为现实。
