共找到2條詞條名為LIS的結果 展開

LIS

最長上升子序列（計算機科學）

最長上升子序列（Longest Increasing Subsequence，LIS），在計算機科學上是指一個序列中最長的單調遞增的子序列。

目錄
1實現 2應用

實現

有兩種，時間複雜度分別為O(n^2)與O(n log n)，空間複雜度均為O(n)。
O(n^2)的方法：
O(n log n)的方法：

應用

LIS經常用於確定一個代價最小的調整方案，使一個序列變為升序。只需要固定LIS中的元素，調整其他元素即可。

基本信息