题目描述

难度分:$1300$

输入$T(\leq 2 \times 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

每组数据输入$n(2 \leq n \leq 10^5)$和一个$1$~$n$的排列$p$。

选一个$p$的长度至少为$2$的子序列$b$，最大化$b$的所有相邻元素的绝对差的和。

即$S=|b_1-b_2|+|b_2-b_3|+…$

在$S$最大的前提下，$b$的长度尽量小。输出任意一个符合要求的$b$。

注：子序列不一定连续。

输入样例

2
3
3 2 1
4
1 3 4 2

输出样例

2
3 1 
3
1 4 2 

算法

贪心构造

观察一下可以发现一个事实：当给你的是一个单调数组时，最划算的方式就是选首尾两个元素构成一个长度为$2$的子序列，这样和你选超过两个元素得到的$S$值是一样的。

有了这个结论问题就迎刃而解了，$a[1]$和$a[n]$是必须要选的，对于中间的$i \in [2,n-1]$，只要满足$a[i]$是峰（$a[i] \gt max(a[i-1],a[i+1])$）或者谷（$a[i] \lt min(a[i-1],a[i+1])$），就选上。

复杂度分析

时间复杂度

仅遍历了一遍数组$a$就得到了答案，因此算法的时间复杂度为$O(n)$。

空间复杂度

出了原数组$a$，以及要返回的子序列$seq$（其实这个空间也是可以省掉的，在构造的过程中直接打印），仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

$python$代码

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    seq = [a[0]]
    for i in range(1, n - 1):
        if a[i] > max(a[i - 1], a[i + 1]):
            seq.append(a[i])
        elif a[i] < min(a[i - 1], a[i + 1]):
            seq.append(a[i])
    seq.append(a[n - 1])
    print(len(seq))
    for num in seq:
        print(num, end=' ')
    print()