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項數值。

計算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] << ' ';
}