N * logN的最大上升子序列（附标程） - O興~

又很久没写了。我在我们那个判题系统中的工作终于暂告一段落，下周的校内选拔赛可以用上了。说实话，这个系统我看来在国际上都占居先进地位。我还没见过更好的。现在主流的PC^2比起我们的系统，其它的不说，在题目的定义上就差了很多。上几个星期我们内部练习赛的时候就出了问题，裁判把输出文件放到了输入文件的位置，导致我一直Runtime Error。在我们的系统中有题目的自检，就不会出这种事。
当然这个系统还是有很多很不足的地方，09年办地区赛之前我们得继续把它做好。到时候能把它推向国际就最好了。

最近学会了一个N * logN的最大上升子序列的算法（LIS：Longest Increasing Subsequence），挺巧妙的，在这里讲一下。
一般的LIS算法，我们用的都是N^2的DP，也就是对每一个数，枚举它前面的所有数，看它跟在谁的后面能构成当前的最大上升子序列。
N * log N的LIS是基于这样一个定理：设tail[i]为所有长度为i的LIS当中最小的一个尾数，则有当i < j时，tail[i] < tail[j]。自已思考一下，举两个例子，这个定理很容易就能想通的。
有了这个定理就好办啦，对于原序列中的每个数seq[i]，我们在tail[1]到tail[len]（len是当前已找到的最长的LIS的长度）中二分搜索小于seq[i]的最大的一个数，这样就可以找到以seq[i]结尾的LIS啦。
算法的细节我就不多说了，下面提供了标程。这个算法还有一个有趣地方，它求出来的LIS是所有LIS中出现的最晚的一个。即如果原序列是3、2、1、6、5、4、9、8、7，输出的是1、4、7。
这个算法可以用在UVA 481上（online-judge.uva.es/p/v4/481.html）。
下面是我的标程，主函数里有测试数据：

#include <iostream>

using namespace std;

//Longest increasing subsequence. (time = n * lgn)
//Returns the length of LIS.
int findLIS(const int* seq, int size, int* output) {
    //tail[i] is the index of the lowest tail out of all LISs of length i.
    int tail[size + 1];
    //pre[i] is the index of previous element seq[i] in LIS.
    int pre[size];

    int len = size > 0? 1: 0;//Length of LIS.
    tail[1] = 0;

    for (int i = 1; i < size; i++) {
        if (seq[i] <= seq[tail[1]]) {
            tail[1] = i;
        }
        else {
            //Find the last tail lower than seq[i].
            int low = 1;
            int high = len;
            while (low < high) {
                int mid = (low + high + 1) / 2;
                if (seq[tail[mid]] < seq[i]) {
                    low = mid;
                }
                else {
                    high = mid - 1;
                }
            }
            tail[low + 1] = i;
            pre[i] = tail[low];
            if (low == len) {
                len++;
            }
        }
    }
    int p = tail[len];
    for (int i = len - 1; i >= 0; i--) {
        output[i] = seq[p];
        p = pre[p];
    }
    return len;
}

//Test suites.
int main() {
    int a[] = {1, 7, 14, 0, 9, 4, 18, 18, 2, 4,
               5, 5, 1, 7, 1, 11, 15, 2, 7, 16};
    int b[20];
    int len = findLIS(a, 20, b);
    cout << len << ": ";
    for (int i = 0; i < len; i++) {
        cout << b[i] << " ";
    }
    cout << endl;
    //Correct output: "8: 0 2 4 5 7 11 15 16".
    return 0;
}