求數(shù)組中最長遞增子序列（Longest Increasing Subsequence, LIS）
LIS問題是算法中的經(jīng)典題目，傳統(tǒng)的解法是使用動態(tài)規(guī)劃，時(shí)間復(fù)雜度是O(n^2)；改進(jìn)的方法時(shí)間復(fù)雜度是O(nlogn)。但是關(guān)于改進(jìn)的算法的介紹盡管網(wǎng)上有很多資源，但是有許多看起來沒問題，但是經(jīng)不起推敲，我看的時(shí)候感覺有點(diǎn)看不明白，查閱半天弄懂后再回去看，發(fā)現(xiàn)他們的表述有問題，因此總結(jié)一下。
這篇總結(jié)使用從傳統(tǒng)解法逐步改進(jìn)的演繹方法，并給出一些推理。
如果讀者不喜歡這種演繹思考方法，推薦Slyar的方法，他從另一個角度看待這個問題，寫得十分簡潔，但是沒有接觸過的話，可能不易理解。
本文仍有許多不足，歡迎指正。
傳統(tǒng)的解法是使用動態(tài)規(guī)劃。原理如下：
data[i]表示數(shù)組中的第i個元素；
lis[i]表示以元素i結(jié)尾的最長遞增子序列長度；
那么lis[i] = max(lis[j]) + 1, j ∈{k | data[k] < data[i], k < i}
時(shí)間復(fù)雜度是O(n^2)，它的主要優(yōu)點(diǎn)是算法簡單，可以構(gòu)造最長遞增子序列。
int lis[N];
int LIS_DP(int* data, int n)
{
memset(lis, 1, n * sizeof(lis[0]));
for(int i=1; i != n; ++i)
{
for(int j=0; j != i; ++j)
{
if(data[i] > data[j] && lis[i] < lis[j]+1)
lis[i] = lis[j] + 1;
}
}
int max = 0;
for(int i=0; i != n; ++i)
if(max < lis[i])
max = lis[i];
return max;
}
另一種方法稍微有些復(fù)雜，它是針對上面方法的一種改進(jìn)，時(shí)間復(fù)雜度是O(nlogn)。下面使用漸近的方法來分析獲得。
首先我們來分析一下上面算法的不足，在上面的求解中，每個lis[i]求解的時(shí)間復(fù)雜度是O(n)，但這不是必需的
0 1 2 3 4 5 6 7
data[]: 2 5 6 2 3 4 7 4
lis[]: 1 2 3 1 2 3 4 3
例如，當(dāng)求lis[6]時(shí)，是不用和data[3]、data[4]比較的，因?yàn)橐呀?jīng)知道它們所在的最大遞增子序列的最后一個元素data[5] < data[6]；也就是說，當(dāng)我們考察第i個元素時(shí)，對前面i-1個元素的任何一個遞增子序列，如果這個子序列的最后一個元素比data[i]小，那么就可以將data[i]加在這個子序列后面，構(gòu)成一個新的更長的遞增子序列，而不用比較這個子序列前面的元素和data[i]的關(guān)系。
由此我們得出第一個啟發(fā)式方法，當(dāng)計(jì)算lis[i]時(shí)，我們只關(guān)心每個前i-1元素中遞增子序列的最后一個元素的值。
針對第一種方法引入的觀點(diǎn)，提出第二個啟發(fā)式方法，同樣求lis[6]，對前i-1個元素，獲得兩個長度為3的遞增子序列2、5、6和2、3、4，此時(shí)已知data[6] > 6且data[6]大于4，所以data[6]可以接在任何一個子序列后面，構(gòu)成長度為4的新遞增序列。這個時(shí)候，會發(fā)現(xiàn)一個啟發(fā)方法，data[6]不用和6比較，因?yàn)橹恍?/span>data[6]大于4就可以得出一個長度為4的遞增序列。
所以得出第二個啟發(fā)式方法，當(dāng)計(jì)算lis[i]時(shí)，對同樣長度的子序列，我們只關(guān)心它們最后元素的值最小的一個的值。
由此，由一個數(shù)組last_min記錄上面的值，即當(dāng)計(jì)算lis[i]時(shí)，last_min[k]表示前i-1個元素中長度為k的所有遞增子序列的最后一個元素的最小值。
設(shè)max_len表示當(dāng)前已獲得的最長的遞增子序列。
當(dāng)考察data[i]時(shí)，如果data[i] > last_min[max_len]，那么將data[i]接在這個序列后面，便構(gòu)成一個新的長度為max_len+1的序列，該序列的最后一個元素是data[i]；否則，找到一個最大的j，使last_min[j]<data[i]（由于查找方式，也說明data[i]<=last_min[j+1]），那么把data[i]接在這個序列后面，便構(gòu)成一個長度為j+1的新序列，更新last_min[j+1]。
int lis[N]; // lis[i]表示以元素i結(jié)尾的最長遞增子序列長度
int last_min[N]; // last_min[i]表示長度為i的所有遞增子序列的
// 最后一個元素的最小值
int max_len;
int LIS_DP(int* data, int n)
{
memset(lis, 1, n * sizeof(lis[0]));
last_min[1] = data[0];
max_len = 1;
for(int i=1; i != n; ++i)
{
// 如果data[i]比最長遞增序列的最后一個元素大，
// 那么直接加在它后面便可
if (data[i] > last_min[max_len])
{
++max_len;
last_min[max_len] = data[i];
lis[i] = max_len;
}
else
{
// 否則查找歷史最長遞增序列
for(int j=max_len-1; j != 0; --j)
{
if (data[i] > last_min[j]) // 也就是說，data[i] <= last_min[j+1]
{
lis[i] = j + 1;
last_min[j+1] = data[i]; //更新
break;
}
}
}
}
return max_len;
}
如上所示，雖然已經(jīng)進(jìn)行了很大的優(yōu)化，但是當(dāng)前的時(shí)間復(fù)雜度仍是O(n^2)，當(dāng)然基本可以確定的是，現(xiàn)在的算法比原來的效率提高了很多。
下面我們分析一下last_min數(shù)組的性質(zhì)，
由定義last_min[i]表示長度為i的序列A的最后一個元素的值，last_min[i-1]表示長度為i-1的序列B的最后一個元素的值，那么last_min[i-1]<last[i]；否則序列A的前i-1個元素構(gòu)成的序列便可替代序列B。所以last_min是有序的。
因此在上面的查找中可以使用二分查找，效率為O(logn)，使得總的復(fù)雜度為O(nlogn)。
// 返回arr中等于或第一個大于val的位置
int BinarySearch(int* arr, int left, int right, int val)
{
int mid = 0;
int l = left;
int r = right;
while (l <= r)
{
mid = (l + r) >> 1;
if (arr[mid] > val) r = mid - 1;
else if (arr[mid] < val) l = mid + 1;
else return mid;
}
return l;
}
int last_min[N]; // last_min[i]表示長度為i的所有遞增子序列的
// 最后一個元素的最小值
int max_len;
int LIS_DP(int* data, int n)
{
last_min[1] = data[0];
max_len = 1;
for(int i=1; i != n; ++i)
{
// 如果data[i]比最長遞增序列的最后一個元素大，
// 那么直接加在它后面便可
if (data[i] > last_min[max_len])
{
++max_len;
last_min[max_len] = data[i];
}
else
{
// 否則查找歷史最長遞增序列
int j = BinarySearch(last_min, 1, max_len, data[i]);
last_min[j] = data[i];
}
}
return max_len;
}
在程序二中，lis數(shù)組完全沒有作用，所以在程序三中沒有使用。
與程序一相比，程序三在效率上有明顯的提升，但是不能根據(jù)last_min構(gòu)造出最長遞增子序列。
參考文獻(xiàn)
編程之美—微軟技術(shù)面試心得.2.16節(jié)