给定一个长度为 n 的整数序列 a1, a2, …, an

n 个序列 a 连续拼接在一起,从而得到一个新序列。

请你计算,新序列的最长严格递增子序列的长度。

注意,子序列不一定连续。

例如,当 a 为 [3, 2, 1] 时,将 3 个 a 连续拼接在一起,得到 [3, 2, 1, 3, 2, 1, 3, 2, 1],其最长严格递增子序列为 [1, 2, 3]。

输入格式

第一行包含整数 T,表示共有 T 组测试数据。

每组数据第一行包含一个整数 n

第二行包含 n 个整数 a1, a2, …, an

输出格式

每组数据输出一行结果,一个整数,表示新序列的最长严格递增子序列的长度。

数据范围

前 5 个测试点满足 1 ≤ T ≤ 51 ≤ n ≤ 10

所有测试点满足 1 ≤ T ≤ 200001 ≤ n ≤ 1051 ≤ ai ≤ 109,一个测试点内所有 n 的相加之和不超过 105。

输入样例

2
3
3 2 1
6
3 1 4 1 5 9

输出样例

3
5

代码实现

#include <iostream>
#include <unordered_set>
using namespace std;

int t, n, x;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) {
        cin >> n;
        unordered_set <int> h;
        while(n--) {
            cin >> x;
            h.insert(x);
        }
        cout << h.size() << '\n';
    }
    return 0;
} 
分类: Thought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status