最长公共子序列 O(NlogN) 做法

题意：略

思路：O（NlogN）

1.相同长度的子序列仅需要保存最小的一个;

2.且随着长度的增长,该最小值递增;

     证明：可用反证法.
             假设长度为 5 的最小值大于长度为 6 的最小值，则长度为 6 的序列的倒数第二个数也就是
     某长度为 5 的序列最小值,显然和我们保存的长度为 5 的最小值矛盾，故证明成立。

3.故有解法：
         遍历序列,维护一个长度对应序列的数组,对于Ai，在数组中查找合适的值，例如找到了长度为len的x,
        然后更新长度为len + 1的最小值（因为Ai一定是大于min[len]，小于min[len + 1]的）.

时间复杂度：O（NlogN）约等于 1e6*20 == 2000万.

自己的代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;

int n, a[N];
int ans, mini[N];

int main (){
    scanf("%d", & n);
    for (int i = 1; i <= n; i ++ ) 
        scanf("%d", & a[i]);
    int len = 0;
    for (int i = 1; i <= n; i ++ ) {
        int l = 1, r = len, mid, tmp = 0;
        while (l <= r) {
            mid = l + r >> 1;
            if (mini[mid] < a[i]) tmp = mid, l = mid + 1;
            else r = mid - 1;
        }
        len = max(len, tmp + 1);
        mini[tmp + 1] = a[i];
    }
    cout << len << endl;
    return 0;
}

THE END;