C++

C++ – LIS 最长上升子序列问题

_Redstone_c_

基础解法[O(N^2)]

T为输入的序列,F为以第i个数结尾的最长上升子序列长度

可得到F[i]等于F[0 …… i – 1]中满足T[i] > T[0 …… i – 1]的数

例如序列T = {1, 5, 6, 4, 2, 9} 对应的F = {1, 2, 3, 2, 2, 4}

F序列中最大的数即为最长上升子序列

void LIS() {
    for(int i = N; i >= 1; i--) {
        max = 0;
        for(int j = N; j > i; j--)
            if(max < TB[j] && T[j] < T[i]) max = TB[j];
        TB[i] = max + 1;
    }
}

优化解法[O(N log N)]

可以直接求到i的最长子序列长度

可以再创建一个数组 (队列?) queue,以其长度表示 到i的最长子序列长度

可以一个一个将T中的数据加入进来并且维护其为上升状态

当出现数字小于末尾数字时,将其替换第一比他大的元素

例如序列T = {1, 5, 6, 4, 2, 9} [用back表示queue的最后一位元素下标]

插入1 : queue = {1} back = 1

插入5 : queue = {1, 5} back = 2

插入6 : queue = {1, 5, 6} back = 3

插入4 : queue = {1, 4, 6} back = 3

插入2 : queue = {1, 2, 6} back = 3

插入9 : queue = {1, 2, 6, 9} back = 4 

void add(int x) {
    for(int i = 1; i <= back; i++) {
        if(queue[i] >= x) {
            queue[i] = x;
            return;
        }
    }
    queue[++back] = x;
}

现在时间复杂度还是O(N ^ 2)

因为queue是上升序列,所以可以使用二分查找优化插入处理为log N

int bs(int start, int end, int x) {
    if(start >= end) return start;
    int mid = (end - start) / 2 + start;
    if(queue[mid] >= x) return bs(start, mid, x);
    return bs(mid + 1, end, x);
}
void add(int x) {
    int temp = bs(0, back, x);
    queue[temp] = x;
    if(temp == back) back++;
}

发表回复