给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）例如：给定一个长度为8的数组A{1,3,5,2,4,6,7,8}，则其最长的单调递增子序列为{1,2,4,6,7,8}，长度为6.
输入描述:
第一行包含一个整数T，代表测试数据组数。对于每组测试数据：N-数组的长度a1 a2 ... an （需要计算的数组）保证：1<=N<=3000,0<=ai<=MAX_INT.

输出描述:
对于每组数据，输出一个整数序列，代表最长递增子序列。若有多组最长上升子序列，输出第一组。保证：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;
}