Week 6: LIS(Longest Increasing Subsequence )

• increasing: 嚴格遞增
• subsequence: sub + sequence 。 sub 有著「次要」的意思，而 sequence 是指數學之中的「數列」、「序列」。
• LIS: 指一個 sequence 當中，它擁有最長的長度、且嚴格遞增的那些 subsequence （不一定只有一個）。
  • ex.1 3 5 2 9 的 LIS 是 1 3 5 9 這個 subsequence 。

##Dynamic Programming 概念

Recurence:
length(n) =  max  { length(i) + 1 : if s[i] < s[n] }    ( 0≤i≤n-1)
n：第0項到第n項的LIS。
length(n)：第0項到第n項的LIS長度。
s[n]：第n項數值。

時間複雜度： O(N^2)

計算LIS長度

int s[5];       // sequence
int length[5];  // 第 x 格的值為 s[0...x] 的 LIS 長度
 
void LIS()
{
    // 初始化。每一個數字本身就是長度為一的 LIS。
    for (int i=0; i<5; i++) length[i] = 1;
 
    for (int i=0; i<5; i++)
        // 找出 s[i] 後面能接上哪些數字，
        // 若是可以接，長度就增加。
        for (int j=i+1; j<5; j++)
            if (s[i] < s[j])
                length[j] = max(length[j], length[i] + 1);
 
    // length[] 之中最大的值即為 LIS 的長度。
    int n = 0;
    for (int i=0; i<5; i++)
        n = max(n, length[i]);
    cout << "LIS的長度是" << n;
}

找出LIS

/*用一個陣列紀錄一個數字是接在哪個數字後面*/

int s[5];
int length[5];
int prev[5]; // prev[x] 紀錄 s[x] 是接在哪個數字後面
 
void LIS()
{
    for (int i=0; i<5; i++) length[i] = 1;
    // -1 代表 s[i] 是開頭數字，沒有接在其他數字後面。
    for (int i=0; i<5; i++) prev[i] = -1;
 
    for (int i=0; i<5; i++)
        for (int j=i+1; j<5; j++)
            if (s[i] < s[j])
                if (length[i] + 1 > length[j])
                {
                    length[j] = length[i] + 1;
                    // s[j] 接在 s[i] 後面
                    prev[j] = i;
                }
 
    int n = 0, pos = 0;
    for (int i=0; i<5; i++)
        if (length[i] > n)
        {
            n = length[i];
            pos = i;
        }
 
    trace(pos); // 印出一個LIS
}
 
// 遞迴版本
void trace(int i)
{
    if (prev[i] != -1) trace(prev[i]);
    cout << seq[i] << ' ';
}
 
// 迴圈版本，但是順序會顛倒。
void trace(int i)
{
    for (; prev[i] != -1; i = prev[i])
        cout << seq[i] << ' ';
}

##Robinson-Schensted-Knuth Algorithm 概念

採取 Greedy 策略，以 Binary Search 加速，達到 O(NlogL) ， N 是給定序列的長度， L 是 LIS 的長度。

時間複雜度： O(NlogN)

計算LIS長度

int LIS(vector<int>& s)
{
    // 不得不判斷的特例
    if (s.size() == 0) return 0;
 
    // 先放入一個數字，免得稍後 v.back() 出錯。
    vector<int> v;
    v.push_back(s[0]);
 
    for (int i = 1; i < s.size(); ++i)
    {
        int n = s[i];
 
        if (n > v.back())
            v.push_back(n);
        else
            *lower_bound(v.begin(), v.end(), n) = n;
    }
 
    return v.size();
}

找出LIS

sequence : -7 10  9  2  3  8  8  1
temp LIS :
position :
 
sequence :(-7)10  9  2  3  8  8  1
temp LIS : -7
position :  1       // -7 在 LIS 的第一個位置
 
sequence : -7(10) 9  2  3  8  8  1
temp LIS : -7 10
position :  1  2    // 10 在 LIS 的第二個位置，以此類推。
 
sequence : -7 10 (9) 2  3  8  8  1
temp LIS : -7  9
position :  1  2  2
/* 9 成為 LIS 的潛力比 10 大, 所以以 9 代替 10 */
 
sequence : -7 10  9 (2) 3  8  8  1
temp LIS : -7  2
position :  1  2  2  2
/* 2 成為 LIS 的潛力比 9 大, 所以以 2 代替 9 */
 
sequence : -7 10  9  2 (3) 8  8  1
temp LIS : -7  2  3
position :  1  2  2  2  3
 
sequence : -7 10  9  2  3 (8) 8  1
temp LIS : -7  2  3  8
position :  1  2  2  2  3  4
 
sequence : -7 10  9  2  3  8 (8) 1
temp LIS : -7  2  3  8
position :  1  2  2  2  3  4  4
/* 8 成為 LIS 的潛力比 8 大, 所以以 8 代替 8 */
 
sequence : -7 10  9  2  3  8  8 (1)
temp LIS : -7  1  3  8
position :  1  2  2  2  3  4  4  2
/* 1 成為 LIS 的潛力比 2 大, 所以以 1 代替 2 */

首先找到每個數字在 LIS 當中的合適位置 position[] ，接下來就可以從 position[] 裡面找到真正的 LIS 。從尾巴開始往回找，先找到的就是正確的。因為 LIS 長度為 4 ，所以就先找位置為 4 的。

sequence : -7 10  9  2  3  8 (8) 1
position :  1  2  2  2  3  4 (4) 2
LIS      :  -  -  -  8
/* search 4th, 8 is fourth LIS element */
 
sequence : -7 10  9  2 (3) 8  8  1
position :  1  2  2  2 (3) 4  4  2
LIS      :  -  -  3  8
/* search 3rd, 3 is third LIS element */
 
sequence : -7 10  9 (2) 3  8  8  1
position :  1  2  2 (2) 3  4  4  2
LIS      :  -  2  3  8
/* search 2nd, 2 is second LIS element */
 
sequence :(-7)10  9  2  3  8  8  1
position : (1) 2  2  2  3  4  4  2
LIS      : -7  2  3  8
/* search 1st, -7 is first LIS element */

最後得到 LIS 為 -7 2 3 8 。

LIS 可能不止一個。上述方法會得到最後出現的 LIS 。若是要得到最先出現的 LIS ，該怎麼辦呢？最簡單的方式是：原本序列由右至左的做 Longest Decreasing Subsequence 就行了。

##Reference

http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html

https://en.wikipedia.org/wiki/Longest_increasing_subsequence