C++

C++ – LIS longest rising subsequence problem

_Redstone_c_

Basic solution [O(N^2)]

T is the input sequence, and F is the length of the longest ascending subsequence ending with the i-th number.

It can be obtained that F[i] is equal to the number in F[0 …… i – 1] that satisfies T[i] > T[0 …… i – 1]

For example, the sequence T = {1, 5, 6, 4, 2, 9} corresponds to F = {1, 2, 3, 2, 2, 4}

The largest number in the F sequence is the longest ascending subsequence.

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;
    }
}

Optimization solution [O(N log N)]

You can directly find the length of the longest subsequence of i

You can create another array (queue?) queue, whose length represents the length of the longest subsequence to i

You can add the data in T one by one and maintain it in the rising state

When a number is smaller than the last number, replace it with the first element that is larger than it.

For example, the sequence T = {1, 5, 6, 4, 2, 9} [use back to represent the subscript of the last element of the queue]

Insert 1: queue = {1} back = 1

Insert 5: queue = {1, 5} back = 2

Insert 6: queue = {1, 5, 6} back = 3

Insert 4: queue = {1, 4, 6} back = 3

Insert 2: queue = {1, 2, 6} back = 3

Insert 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;
}

Now the time complexity is still O(N ^ 2)

Because the queue is an ascending sequence, binary search can be used to optimize the insertion process to 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++;
}

Post Reply