給定一個長度為N的數(shù)組独郎，找出一個最長的單調自增子序列（不一定連續(xù)，但是順序不能亂）例如：給定一個長度為8的數(shù)組A{1,3,5,2,4,6,7,8}阔蛉，則其最長的單調遞增子序列為{1,2,4,6,7,8}矮嫉，長度為6.
輸入描述:
第一行包含一個整數(shù)T，代表測試數(shù)據(jù)組數(shù)口芍。對于每組測試數(shù)據(jù)：N-數(shù)組的長度a1 a2 ... an （需要計算的數(shù)組）保證：1<=N<=3000,0<=ai<=MAX_INT.
輸出描述:
對于每組數(shù)據(jù)，輸出一個整數(shù)序列雇卷，代表最長遞增子序列鬓椭。若有多組最長上升子序列，輸出第一組关划。保證：1<=T<=20,1<=N<=3000,0<=ai<=MAX_INT.
輸入例子:
2
7
89 256 78 1 46 78 8
5
6 4 8 2 17
輸出例子:
1 46 78
6 8 17
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
int n;
cin >> n;
vector<int> nums(n, 0);
for(int i=0;i<n;i++){
cin >> nums[i];
}
vector<int> keep;
vector<set<int>> pos;
for(int i=0;i<n;i++){
auto it = lower_bound(keep.begin(), keep.end(), nums[i]);
if(it!=keep.end()){
(pos.begin() + (it-keep.begin()))->insert(i);
//替換例如 1小染，3 后面是個2 --->替換為1， 2
*it = nums[i];
}
else{
pos.push_back({i});
keep.push_back(nums[i]);
}
}
vector <int> ans;
for(auto iter = pos.rbegin(); iter!=pos.rend(); iter++){
const set<int> &tmp = *iter;
if(ans.empty()){
ans.push_back(*tmp.begin());
}
else{
for(const auto &t : tmp){
if (nums[t]<nums[ans.back()]){
ans.push_back(t);
break;
}
}
}
}
//倒著輸出
for(auto iter = ans.rbegin(); iter!=ans.rend(); iter++){
cout << nums[*iter];
if(iter+1 != ans.rend()) cout << " ";
}
if(T) cout << endl;
}
return 0;
}
