题意

给出一个长度为$n (2≤n≤10^5)$的排列$p$（其中的每一个元素1到n只出现一次），找到它的子序列$s1, s2, …, sk$至少长度为2，使：

• $|s1−s2|+|s2−s3|+…+|sk−1−sk|$的值最大。
• p至少有长度2.
• 在所有这些子序列中，长度越小越好。
• 如果多个子序列满足这些条件，找到其中的任何一个。

题解

答案包含第一个元素，最后一个元素，以及所有的局部极小值和极大值，其中局部最小值小于它的两个邻接，而局部最大值是一个大于它两个邻接的元素。

证明：
如果$a>b且b>c$或者如果$a<b且b<c$, 则$|a−b|+|b−c|=|a−c|$，所以可以用a和c实现更短的子序列。抹去所有的b，将得到第一个元素，最后一个元素，以及局部极小和极大值。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef long long LL;
const int INF=0x3f3f3f3f;

const int N=1e5+10;
int a[N];
int n;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;

        for(int i=0;i<n;i++) cin>>a[i];
        vector<int>res;
        res.push_back(a[0]);
        for(int i=1;i<n-1;i++)
        {
            if(a[i] > a[i-1] && a[i] > a[i+1]) res.push_back(a[i]);
            else if(a[i] < a[i-1] && a[i] < a[i+1]) res.push_back(a[i]);
        }
        res.push_back(a[n-1]);

        cout<<res.size()<<endl;
        for(auto t:res)
            cout<<t<<' ';
        cout<<endl;

    }

   // system("pause");
}