最長遞增子串列

在計算機科學中，最長遞增子序列（longest increasing subsequence）問題是指，在一個給定的數值序列中，找到一個子序列，使得這個子序列元素的數值依次遞增，並且這個子序列的長度儘可能地大。

基本介紹

• 中文名：最長遞增子串列
• 外文名：longest increasing subsequence
• 學科：計算機

簡介

最長遞增子序列中的元素在原序列中不一定是連續的。許多與數學、算法、隨機矩陣理論、表示論相關的研究都會涉及最長遞增子序列。解決最長遞增子序列問題的算法最低要求O(nlogn)的時間複雜度，這裡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
  

算法

算法（algorithm），在數學（算學）和計算機科學之中，為任何良定義的具體計算步驟的一個序列，常用於計算、數據處理和自動推理。精確而言，算法是一個表示為有限長列表的有效方法。算法應包含清晰定義的指令用於計算函式。

算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和初始輸入（可能為空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在內的一些算法，包含了一些隨機輸入。

形式化算法的概念部分源自嘗試解決希爾伯特提出的判定問題，並在其後嘗試定義有效可計算性或者有效方法中成形。這些嘗試包括庫爾特·哥德爾、雅克·埃爾布朗和史蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函式，阿隆佐·邱奇於1936年提出的λ演算，1936年埃米爾·萊昂·珀斯特的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化算法的情況。