以前搞算法的时候看到过这个算法，但是没有仔细钻研过，似懂非懂，这两天看了看，总算是搞明白了。
问题的背景我就不多说了，相信通过搜索引擎来到这里的都是为了寻求简单易懂的nlogn的答案。
这个算法dp的状态有点诡异：
dp[i] = 长度为i+1的上升子序列中末尾元素的最小值（没有某个长度的上升自序列的话相应位置是无穷大）
初看有点不太明白，为什么是末尾的最小值呢？为什么可以求出最长的公共子序列呢？为什么可以到nlogn呢？别急，我慢慢说。
首先，当这个算法执行完毕的时候，dp数组中的每一个都符合我们定义的状态，每个长度的上升子序列末尾最小值都有了。那么我们看看含有末尾最小值的最大的位置是什么就能找到问题的解了。
其次，我们怎么去进行状态的推算和更新？其实，这个算法已经是优化过的算法，搞的人都不清楚他要干啥了。这个算法的原始版本其实还有一维（详见PSS），如果我们知道N个元素组成的dp数组，那么如果这时候又来了一个元素怎么办？dp数组能很快更新么？必须是可以的。只要新来的元素比dp数组中的某个位置j上的元素大就可以了，那么新来的元素就可以更新dp[j]了，具体是if(dp[j-1]<new) dp[j] = min(dp[j],new),奉上代码:
for( int i = 0; i < n; i++ ){// index for arrays
for( int j = 0; j < n; j++ )// index for dp
if( j == 0 || (dp[j-1] < a[i] && a[i] < dp[j] ) )
dp[j] = a[i];
}
上面简单的代码有个奇特的性质，就是每次循环完dp是单调递增的（除了无穷大），为什么呢，假如dp[3]>dp[5]，长度为5的上升子序列的最后一位最小值竟然比长度为3的末尾最小值小，那我们拿长度为5的上升自序列的后面三个数更新dp[3]不就行了？
最后还有个性质，从上面代码的if语句中可以看出，因为dp是递增的，所以a[i]最多也就更新一次。不妨用二分找出更新的位置，然后复杂度就降到nlogn，你说优美不？
贴上《挑战程序设计竞赛》，65页的代码，大家好好品味
int dp[MAX_N];
void solve{
fill( dp, dp + n, INF );
for( int i = 0; i < n; i++ )
*lower_bound( dp, dp + n, a[i] ) = a[i];
printf("%d\n", lower_bound(dp,dp+n,INF) - dp );
}
什么？没看懂？再看一遍吧。。
PS:以上代码未经验证
PSS：原始算法什么的是我想出来的，为了使思维过程更清晰一点，具体有没有就不知道了
PSSS：有人知道最长不下降自序列可以用nlogn的算法解么？