d242 - 00481 - What Goes Up
題目描述
題目要求找出給定整數序列中最長嚴格遞增子序列 (Longest Increasing Subsequence, LIS) 的長度，並輸出該子序列。如果存在多個長度相同的 LIS，則輸出在原始序列中最後出現的那個。
解題思路
本題使用一種結合了動態規劃和二分搜尋的演算法來求解 LIS。核心思想是維護一個 lis 陣列，其中 lis[i] 儲存所有長度為 i+1 的遞增子序列的最小尾部元素。
對於輸入序列中的每個元素 n，我們執行以下操作：
- 如果
n大於lis陣列中已有的最大元素（即lis[it-1]，其中it是目前已知的 LIS 長度），則將n添加到lis陣列的末尾，並將it增加 1。 - 否則，使用二分搜尋在
lis陣列中找到第一個大於等於n的元素，並將該元素替換為n。
同時，使用 v 陣列記錄每個輸入元素對應的 lis 陣列中的位置。在計算完 LIS 的長度後，我們從輸入序列的末尾開始回溯，根據 v 陣列重建 LIS。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int lis[500001],v[500001],a[500001],it,n,k;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
a[k]=n;
if(it==0||n>lis[it-1]){
lis[it]=n;
++it;
v[k]=it;
}
else{
int tmp=(lower_bound(lis,lis+it,n)-lis);
v[k]=tmp+1;
lis[tmp]=n;
}
++k;
}
cout << it << "\n-\n";
int itt=it;
for(int i=k-1;i>=0&⁢--i){
if(v[i]==it){
lis[it]=a[i];
--it;
}
}
for(int i=1;i<=itt;++i)
cout << lis[i] << "\n";
}