版本 2117c010cec1e5246d28b3aab4a373365f53c29a
Changes from 2117c010cec1e5246d28b3aab4a373365f53c29a to current
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>
