题意描述
Given a permutation p of length n, find its subsequence s1, s2, …, sk of length at least 2 such that:
|s1−s2| |s2−s3| … |sk−1−sk| is as big as possible over all subsequences of p with length at least 2. Among all such subsequences, choose the one whose length, k, is as small as possible. If multiple subsequences satisfy these conditions, you are allowed to find any of them.
A sequence a is a subsequence of an array b if a can be obtained from b by deleting some (possibly, zero or all) elements.
A permutation of length n is an array of length n in which every element from 1 to n occurs exactly once.
寻找子序列，要求相邻两个数的绝对值和最大，并且序列长度最小
思路
我们发现有两种情况：
通过观察可以发现，首尾需要添加。然后寻找峰值即可。
AC代码
代码语言：javascript复制#include<bits/stdc .h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x )
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=1e5 10;
const int M=1e6 10;
const int INF=0x3f3f3f3f;
const int MOD=1e9 7;
int a[N];
void solve(){
int n;cin>>n;
rep(i,1,n 1) cin>>a[i];
vector<int> ans;
ans.PB(a[1]);
rep(i,2,n){
if(a[i-1]<a[i] && a[i]>a[i 1]){
ans.PB(a[i]);
}
if(a[i-1]>a[i] && a[i 1]>a[i]){
ans.PB(a[i]);
}
}
ans.PB(a[n]);
cout<<ans.size()<<endl;
rep(i,0,ans.size()) cout<<ans[i]<<' ';
cout<<endl;
}
int main(){
IOS;
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
