基本介紹
- 中文名：最長遞增子序列
- 外文名：longest increasing subsequence
最長遞增子序列問題,與其他算法問題的關係,高效的算法,長度範圍,線上算法,例子,代碼,
最長遞增子序列問題
問題描述：
給定正整數序列x1,···,xn。
（1）計算其最長遞增子序列的長度s。
（2）計算從給定的序列中最多可取出多少個長度為s的遞增子序列。
（3）如果允許在取出的序列中多次使用x1和 xn，則從給定序列中最多可取出多少個長度為s的遞增子序列。12345。
編程任務：
設計有效算法完成（1）（2）（3）提出的計算任務。
數據輸入：
由檔案input.txt提供輸入數據。檔案第1行有1個正整數n，表示給定序列的長度。接下來的1行有n個正整數x1,···,xn。
結果輸出：
程式運行結束時，將任務（1）（2）（3）的解答輸出到檔案 output.txt中。第1 行是最長遞增子序列的長度s。第2行是可取出的長度為s的遞增子序列個數。第3行是允許在取出的序列中多次使用x1和xn時可取出的長度為s的遞增子序列個數。
輸入檔案示例：
input.txt 43 6 2 5
輸出檔案示例：
output.txt223
與其他算法問題的關係
最長的子序列問題與最長公共子序列問題密切相關，後者具有二次時間動態規劃解：序列S的最長增長子序列是S和T的最長公共子序列，其中T是排序S的結果但是，對於輸入是整數1,2，...，n的排列的特殊情況，這種方法可以更有效，導致形式O的時間範圍（n log log n）。
置換圖中最大的集團由定義圖的置換的最長遞減子序列定義;最長的遞減子序列在計算複雜度上等同於所有數字的否定，等於最長的增加子序列。因此，可以使用增長最長的子序列算法在置換圖中有效地解決集團問題。
在置換與Young tableaux之間的Robinson-Schensted對應關係中，對應於置換的畫面的第一行的長度等於置換的最長增加子序列的長度，並且第一列的長度等於最長的長度。減少子序列。
高效的算法
下面概述的算法通過數組和二進制搜尋有效地解決了增長最長的子序列問題。它按順序處理序列元素，保持到為止發現的最長的增長子序列。將序列值表示為X[0]，X[1]等。然後，在處理X[i]之後，算法將存儲兩個數組中的值：
M[j]----存儲最小值X[k]的索引k，使得在範圍k≤i上存在以X[k]結尾的長度j的增加子序列。注意，j≤（i + 1），因為j≥1表示增加子序列的長度，k≥0表示其終止的索引。
P[k]----將X[k]的前驅者的索引存儲在以X[k]結尾的最長增加子序列中。
此外，該算法存儲變數L，該變數L表示為止發現的最長增長子序列的長度。因為下面的算法使用從零開始的編號，為了清楚起見，M用M[0]填充，其未被使用，使得M[j]對應於長度為j的子序列。真正的實現可以跳過M[0]並相應地調整索引。
注意，在算法的任何一點，序列X[M[1]]，X[M[2]]，...，X[M[L]]
在增加。因為，如果在X [M[j]]處結束的長度j≥2的子序列越來越多，那么也存在以較小值結束的長度j-1的子序列：即以X [P[M]結束的一個子序列[J]]]。因此，我們可以在對數時間內以此順序進行二進制搜尋。
然後，算法進行如下：
P = array of length N M = array of length N + 1 L = 0 for i in range 0 to N-1: // Binary search for the largest positive j ≤ L // such that X[M[j]] < X[i] lo = 1 hi = L while lo ≤ hi: mid = ceil((lo+hi)/2) if X[M[mid]] < X[i]: lo = mid+1 else: hi = mid-1 // After searching, lo is 1 greater than the // length of the longest prefix of X[i] newL = lo // The predecessor of X[i] is the last index of // the subsequence of length newL-1 P[i] = M[newL-1] M[newL] = i if newL > L: // If we found a subsequence longer than any we've // found yet, update L L = newL // Reconstruct the longest increasing subsequence S = array of length L k = M[L] for i in range L-1 to 0: S[i] = X[k] k = P[k] return S
因為該算法對每個序列元素執行單個二進制搜尋，所以其總時間可以使用Big O表示法表示為
。 Fredman（1975）討論了這種算法的一種變體，他將其歸功於Donald Knuth; 在他研究的變體中，該算法測試在進行二分搜尋之前，每個值X[i]是否可以用於在恆定時間內擴展當前最長的增加序列。 通過這種修改，該算法在最壞的情況下使用最多
比較，這對於基於比較的算法而言是最佳的，直到
項中的常數因子。
長度範圍
根據Erdős-Szekeres定理，任何
個不同整數的序列都有一個增加或減少的長度為n+1的子序列。對於其中輸入的每個排列同樣可能的輸入，最長增加子序列的預期長度約為
。在n接近無窮大的極限中，隨機置換n個項的序列的最長增長子序列的長度具有接近Tracy-Widom分布的分布，高斯單一中隨機矩陣的最大特徵值的分布合奏。
線上算法
線上算法的設定中也研究了最長的增長子序列，其中一系列具有連續分布的獨立隨機變數的元素F-或者隨機置換的元素 ——一次一個地呈現給算法。必須決定是否包含或排除每個元素，而不了解後面的元素。在該問題的變體中，其允許在若干上下文中的有趣套用，可以設計最佳選擇過程，給定大小為n的隨機樣本作為輸入，將生成具有最大預期長度大小的增加序列
。通過該最優程式選擇的增加子序列的長度具有近似等於
的方差，並且在通常的中心和縮放之後其限制分布是漸近正態的。在泊松到達過程的設定中，相同的漸近結果對於相應的問題具有更精確的界限。泊松過程設定的進一步改進是通過最優選擇過程的中心極限定理的證明給出的，該定理以合適的歸一化保持比人們預期的更完整的意義。證明不僅產生“正確的”功能極限定理，而且產生總結所有相互作用過程的三維過程的（奇異）協方差矩陣。
例子
對於以下的原始序列
- 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
最長遞增子序列為
- 0, 2, 6, 9, 11, 15.
值得注意的是原始序列的最長遞增子序列並不一定唯一，對於該原始序列，實際上還有以下兩個最長遞增子序列
- 0, 4, 6, 9, 11, 15 或 0, 4, 6, 9, 13, 15
代碼
C++實現：
void getDP(int *arr, int *dp, int len)
{
for (int i = 0; i < len; i++)
{
dp[i] = 1;
for (int j = 0; j < i; j++)
{
if (arr[j] < arr[i] && (dp[j] + 1) > dp[i])
{
dp[i] = dp[j] + 1;
}
}
}
}
void generateLIS(int *arr, int arrLen, int *dp, int dpLen, int *lis, int& lisLen)
{
int index = 0;
int len = 0;
for (int i = 0; i < dpLen; i++)
{
if (dp[i] > len)
{
len = dp[i];
index = i;
}
}
lisLen = len;
lis[--len] = arr[index];
for (int i = index - 1; i >=0; i--)
{
if (arr[i] < arr[index] && dp[i] == dp[index] - 1)
{
lis[--len] = arr[i];
index = i;
}
}
}
void getLIS(int *arr, int len, int *lis, int& lisLen)
{
if (NULL == arr || NULL == lis)
{
return;
}
int *dp = new int[len];
getDP(arr,dp,len);
generateLIS(arr,len,dp,len,lis,lisLen);
delete[] dp;
}
int main(int argc, char* argv[])
{
int arr[] = {2,1,5,3,6,4,8,9,7};
int len = sizeof(arr)/sizeof(arr[0]);
int *lis = new int[len];
getLIS(arr,len, lis,len);
for (int i = 0; i < len; i++)
{
printf("%d ", lis[i]);
}
printf("\n");
delete[] lis;
return 0;
}
