[科普中國(guó)]-最長(zhǎng)遞增子序列

在計(jì)算機(jī)科學(xué)中，最長(zhǎng)遞增子序列（longest increasing subsequence）問(wèn)題是指，在一個(gè)給定的數(shù)值序列中，找到一個(gè)子序列，使得這個(gè)子序列元素的數(shù)值依次遞增，并且這個(gè)子序列的長(zhǎng)度盡可能地大。最長(zhǎng)遞增子序列中的元素在原序列中不一定是連續(xù)的。許多與數(shù)學(xué)、算法、隨機(jī)矩陣?yán)碚?、表示論相關(guān)的研究都會(huì)涉及最長(zhǎng)遞增子序列。解決最長(zhǎng)遞增子序列問(wèn)題的算法最低要求O(n log n)的時(shí)間復(fù)雜度，這里n表示輸入序列的規(guī)模。

最長(zhǎng)遞增子序列問(wèn)題問(wèn)題描述：

給定正整數(shù)序列x1,···,xn。

（1）計(jì)算其最長(zhǎng)遞增子序列的長(zhǎng)度s。

（2）計(jì)算從給定的序列中最多可取出多少個(gè)長(zhǎng)度為s的遞增子序列。

（3）如果允許在取出的序列中多次使用x1和 xn，則從給定序列中最多可取出多少個(gè)長(zhǎng)度為s的遞增子序列。12345。

編程任務(wù)：

設(shè)計(jì)有效算法完成（1）（2）（3）提出的計(jì)算任務(wù)1。

數(shù)據(jù)輸入：

由文件input.txt提供輸入數(shù)據(jù)。文件第1行有1個(gè)正整數(shù)n，表示給定序列的長(zhǎng)度。接下來(lái)的1行有n個(gè)正整數(shù)x1,···,xn。

結(jié)果輸出：

程序運(yùn)行結(jié)束時(shí)，將任務(wù)（1）（2）（3）的解答輸出到文件 output.txt中。第1 行是最長(zhǎng)遞增子序列的長(zhǎng)度s。第2行是可取出的長(zhǎng)度為s的遞增子序列個(gè)數(shù)。第3行是允許在取出的序列中多次使用x1和xn時(shí)可取出的長(zhǎng)度為s的遞增子序列個(gè)數(shù)。

輸入文件示例：

input.txt 43 6 2 5輸出文件示例：

output.txt223與其他算法問(wèn)題的關(guān)系最長(zhǎng)的子序列問(wèn)題與最長(zhǎng)公共子序列問(wèn)題密切相關(guān)，后者具有二次時(shí)間動(dòng)態(tài)規(guī)劃解：序列S的最長(zhǎng)增長(zhǎng)子序列是S和T的最長(zhǎng)公共子序列，其中T是排序S的結(jié)果但是，對(duì)于輸入是整數(shù)1,2，...，n的排列的特殊情況，這種方法可以更有效，導(dǎo)致形式O的時(shí)間范圍（n log log n）。

置換圖中最大的集團(tuán)由定義圖的置換的最長(zhǎng)遞減子序列定義;最長(zhǎng)的遞減子序列在計(jì)算復(fù)雜度上等同于所有數(shù)字的否定，等于最長(zhǎng)的增加子序列。因此，可以使用增長(zhǎng)最長(zhǎng)的子序列算法在置換圖中有效地解決集團(tuán)問(wèn)題。

在置換與Young tableaux之間的Robinson-Schensted對(duì)應(yīng)關(guān)系中，對(duì)應(yīng)于置換的畫面的第一行的長(zhǎng)度等于置換的最長(zhǎng)增加子序列的長(zhǎng)度，并且第一列的長(zhǎng)度等于最長(zhǎng)的長(zhǎng)度。減少子序列。

高效的算法下面概述的算法通過(guò)數(shù)組和二進(jìn)制搜索有效地解決了增長(zhǎng)最長(zhǎng)的子序列問(wèn)題。它按順序處理序列元素，保持到為止發(fā)現(xiàn)的最長(zhǎng)的增長(zhǎng)子序列。將序列值表示為X[0]，X[1]等。然后，在處理X[i]之后，算法將存儲(chǔ)兩個(gè)數(shù)組中的值：

M[j]----存儲(chǔ)最小值X[k]的索引k，使得在范圍k≤i上存在以X[k]結(jié)尾的長(zhǎng)度j的增加子序列。注意，j≤（i + 1），因?yàn)閖≥1表示增加子序列的長(zhǎng)度，k≥0表示其終止的索引。

P[k]----將X[k]的前驅(qū)者的索引存儲(chǔ)在以X[k]結(jié)尾的最長(zhǎng)增加子序列中。

此外，該算法存儲(chǔ)變量L，該變量L表示為止發(fā)現(xiàn)的最長(zhǎng)增長(zhǎng)子序列的長(zhǎng)度。因?yàn)橄旅娴乃惴ㄊ褂脧牧汩_(kāi)始的編號(hào)，為了清楚起見(jiàn)，M用M[0]填充，其未被使用，使得M[j]對(duì)應(yīng)于長(zhǎng)度為j的子序列。真正的實(shí)現(xiàn)可以跳過(guò)M[0]并相應(yīng)地調(diào)整索引。

注意，在算法的任何一點(diǎn)，序列X[M[1]]，X[M[2]]，...，X[M[L]]

在增加。因?yàn)?，如果在X [M[j]]處結(jié)束的長(zhǎng)度j≥2的子序列越來(lái)越多，那么也存在以較小值結(jié)束的長(zhǎng)度j-1的子序列：即以X [P[M]結(jié)束的一個(gè)子序列[J]]]。因此，我們可以在對(duì)數(shù)時(shí)間內(nèi)以此順序進(jìn)行二進(jìn)制搜索。

然后，算法進(jìn)行如下：

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]]