最長遞增子序列

問題描述：

給定正整數序列。

（1）計算其最長遞增子序列的長度s。

（2）計算從給定的序列中最多可取出多少個長度為s的遞增子序列。

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

編程任務：

設計有效演演算法完成（1）（2）（3）提出的計算任務。

數據輸入：

由文件input.txt提供輸入數據。文件第1行有1個正整數n，表示給定序列的長度。接下來的1行有n個正整數。

結果輸出：

程序運行結束時，將任務（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的結果但是，對於輸入是整數的排列的特殊情況，這種方法可以更有效，導致形式O的時間範圍（n log log n）。

置換圖中最大的集團由定義圖的置換的最長遞減子序列定義；最長的遞減子序列在計算複雜度上等同於所有數字的否定，等於最長的增加子序列。因此，可以使用增長最長的子序列演演算法在置換圖中有效地解決集團問題。

在置換與Young tableaux之間的Robinson-Schensted對應關係中，對應於置換的畫面的第一行的長度等於置換的最長增加子序列的長度，並且第一列的長度等於最長的長度。減少子序列。

下面概述的演演算法通過數組和二進位搜索有效地解決了增長最長的子序列問題。它按順序處理序列元素，保持到為止發現的最長的增長子序列。將序列值表示為等。然後，在處理之後，演演算法將存儲兩個數組中的值：

----存儲最小值的索引k，使得在範圍上存在以結尾的長度j的增加子序列。注意，，因為表示增加子序列的長度，表示其終止的索引。

P[k]----將X[k]的前驅者的索引存儲在以X[k]結尾的最長增加子序列中。

此外，該演演算法存儲變數L，該變數L表示為止發現的最長增長子序列的長度。因為下面的演演算法使用從零開始的編號，為了清楚起見，M用M填充，其未被使用，使得M[j]對應於長度為j的子序列。真正的實現可以跳過M並相應地調整索引。

注意，在演演算法的任何一點，序列

在增加。因為，如果在處結束的長度的子序列越來越多，那麼也存在以較小值結束的長度的子序列：即以結束的一個子序列[J]]]。因此，我們可以在對數時間內以此順序進行二進位搜索。

然後，演演算法進行如下：

因為該演演算法對每個序列元素執行單個二進位搜索，所以其總時間可以使用Big O表示法表示為。 Fredman（1975）討論了這種演演算法的一種變體，他將其歸功於Donald Knuth; 在他研究的變體中，該演演算法測試在進行二分搜索之前，每個值X[i]是否可以用於在恆定時間內擴展當前最長的增加序列。通過這種修改，該演演算法在最壞的情況下使用最多比較，這對於基於比較的演演算法而言是最佳的，直到 項中的常數因子。

根據Erdős-Szekeres定理，任何 個不同整數的序列都有一個增加或減少的長度為的子序列。對於其中輸入的每個排列同樣可能的輸入，最長增加子序列的預期長度約為。在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++實現：