最长不降子序列O(nlogn)

最长递增子序列是一个经典的DP题目。
记得最初接触的DP知识就是以它为例学习的。初学的时候能够理解就觉得已经不错了，能够用O(n^2) 写出来AC掉就开心死。后来接触的多了，大多数类似问题用O(n^2) 十有八九TLE，于是又学到了O(nlogn) 的解法，基本上能够解决这些问题。可惜一直用的是模板，却不知道详细原理，直到最近看到Matrix67博客里的解释才真正理解其详细原理。网上类似代码满天飞，却还从来没有看到像样的原理解释。

样例代码

#include "iostream"
using namespace std;
int a[100001],b[100001];
int main(){
        #ifndef ONLINE_JUDGE
                freopen("D:\in.txt","r",stdin);
        #endif
        int  n, left, right, now, i, t;
        while(cin >> n)
        {
			now = -1;
                for(i = 0; i < n;i++)
                {
                        left = 0;
                        right = now;
                        scanf("%d", &t);
                        while(left <= right)
                        {
                                int mid = ( left + right) / 2;
                                if(a[mid] >= t)
                                        right = mid - 1;
                                else
                                        left = mid + 1;
                        }
                        a[left] = t;
                        if(left > now)
                            now++;
                        /* printf("left: %d\n", left);
                        for(int j=i-1;j>=left;j--)
                            a[j+1] = a[j];
                         a[left] = t;
                        */
                        for(int j = 0; j <=now; j++)
                                cout << a[j] << ' ';
                        puts(""); 
                }
                cout << now+1 << endl;
        }
        return 0;
}

解析

数组F就是记录了一组最长上升子序列，当然，这不是唯一一组。F[i] 表示长度为i的上升子序列中最后一个数最小可能是多少。对于读入的每一个数num，找到一个位置p满足 F[p]<num<=F[p+1],然后用num去更新F[p],如果没找到这样的p，则 将num添加到 F 末尾，最长序列长度增1。由于F是单调的，可能以用二分查找来实现查找p，成功将时间复杂度到O(nlogn)。最终f的长度就是最长上升子序列的长度。
下面给组例子，可以清晰的看到整个过程中数组F中的变化。

8 2 7 3 1 5 9 4 8

2

2 7

2 3

1 3

1 3 5

1 3 5 9

1 3 4 9

1 3 4 8

思考

如果将代码中的<改为>，就变为求不降子序列的最少划分。