-
LIS
（最長上升子序列（計算機科學））
鎖定
最長上升子序列（Longest Increasing Subsequence，LIS），在計算機科學上是指一個序列中最長的單調遞增的子序列。
- 中文名
- 最長上升子序列
- 外文名
-
LIS
Longest Increasing Subsequence
LIS實現
樸素DP算法，O(n^2)：
#pragma GCC optimize(3,"Ofast","inline")
//O3優化
#include<cstdio>
#include<algorithm>
using namespace std;
int* a, * f, l, ans;
int main()
{
scanf("%d", &l);
a = new int[l+1]; //動態數組，以適應不同長度的LIS問題
f = new int[l+1];
for (int i = 1, j; i <= l; ++i)
//邊讀邊處理，只需要一層循環
{
scanf("%d", a + i);
for (int j = 0; j < i; j++)
if (a[j] < a[i])
f[i] = max(f[j] + 1, f[i]);
ans = max(ans, f[i]);
}
printf("%d", ans);
return 0;
}優化DP算法，O(n log n)：
#pragma GCC optimize(3,"Ofast","inline")
//O3優化
#include<cstdio>
#include<algorithm>
using namespace std;
int* a, * f, l, ans;
int main()
{
scanf("%d", &l);
a = new int[l]; //動態數組，以適應不同長度的LIS問題
f = new int[l];
for (int i = 0, j; i < l; ++i)
//邊讀邊處理，只需要一層循環
{
scanf("%d", a + i);
//注意下面兩行，這是優化DP算法和樸素DP算法最大的區別
j = lower_bound(f, f + ans + 1, a[i]) - f; //STL
f[j] = a[i];
ans = max(ans, j);
}
printf("%d", ans);
return 0;
}LIS應用
LIS經常用於確定一個代價最小的調整方案，使一個序列變為升序。只需要固定LIS中的元素，調整其他元素即可。
