簡介
最長遞增子序列中的元素在原序列中不一定是連續的。許多與數學、算法、隨機矩陣理論、表示論相關的研究都會涉及最長遞增子序列。解決最長遞增子序列問題的算法最低要求O( nlog n)的時間複雜度，這裡 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年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化算法的情況。
