Longest Increasing Subsequence (LIS)

Reference:

1. 演算法筆記: Longest Increasing Subsequence
2. GeeksforGeeks: Dynamic Programming | Set 3 (Longest Increasing Subsequence)
3. GeeksforGeeks: Longest Increasing Subsequence Size (N log N)

LIS

The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, length of LIS for { 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.

1. Return length of LIS

Time Complexity: O(n^2)

//a: array of number Ex.{1,3,5,2,9}
//LIS_Table: array of int. keep LIS of every position
//n: length of array "a"
void LIS(int *a, int *LIS_Table, int n)
{
    int i, j, res;

    for(i=0; i<n; i++) {
        LIS_Table[i] = 1;
    }
    ////////////////////////////////////////////////////
    //計算自己可以在LIS排在第幾個位置,由第一個數開始
    //ex:  
    //input: {1,3,2}
    //  step1: "1"計算自己排在第一個位置,此時LIS長度為1
    //  step2: "3"計算自己的位置為第二個,此時LIS長度為2
    //  step3: "2"計算自己的位置為第二個,此時LIS長度為2 
    //
    //  由於每次"數"在計算自己在第幾個位置,需要去跟前面
    //  已經計算過自己位置的"數"做比較來計算自己的位置
    //  所以時間複雜度為n平方
    ////////////////////////////////////////////////////
    for(i=0; i<n; i++) {           
        for(j=0; j<i; j++) {
            if(a[j] < a[i]) {
                LIS_Table[i] = max(LIS_Table[i], LIS_Table[j]+1);
            }
        }
    }

    //get MAX_LIS value from LIS_Table
    res=0;
    for(i=0; i<n; i++) {
        res = max(res, LIS_Table[i]);
    }
    printf("length of LIS is %d", res);
}

2. Return length of LIS with Binary Search

Time Complexity: O(NlogN)

這方法是透過Binary Search來讓每個"數"來找自己在LIS的位置,不用去比對每個"數"來計算位置,所以在計算位置的時間上節省了許多

int CeilIndex(int *a, int left, int right, int key)
{
    while(right-left > 1) {
        int m = left + (right - left)/2;

        if(a[m] >= key)
            right = m;
        else
            left = m;
    }
    return right;
}

int LIS(int *a, int size)
{
    int *tailtable = (int*)malloc(sizeof(int) * size);
    int len;

    memset(tailtable, 0, sizeof(tailtable);
    len = 1;

    tailtable[0] = a[0];

    for(int i=1; i<size; i++) {
        if(a[i] > tailtable[len-1])
            tailtable[len++] = a[i];
        else
            tailtable[CeilIndex(tailtable, -1, len-1, a[i])] = a[i];
    }
    //如果想列出LIS,可以從tailtable下手,從後面開始往回找
    //假設LIS長度為3,就從tailtable由後往前找第一個為3的"數"是哪個
    //接著找第一個為2的"數",找到1為止
    //ex:
    //sequence: 1  3  2  4
    //position: 1  2  2  3
    //我們就可列出LIS為"124",列出的LIS為最後一個LIS
    //若要列出第一個LIS,可以做LDS,由右往左的作,就可以列出第一個LIS
    free(tailtable);
    return len;
}