题目链接：https://codeforces.com/contest/1364/problem/B
给出大小为 $n$ 的一个排列 $p$，找出子序列 $s$，使得 $|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$ 最大的同时 $k$ 尽可能地小。
忽略所有位于两个数中间的数。
#include <bits/stdc++.h> using namespace std; bool sorted(int a, int b, int c) { return (a < b and b < c) or (a > b and b > c); } void solve() { int n; cin >> n; int a[n] = {}; for (int i = 0; i < n; i++) cin >> a[i]; int len = n; bool skip[n] = {}; for (int i = 1; i < n - 1; i++) if (sorted(a[i - 1], a[i], a[i + 1])) skip[i] = true, --len; cout << len << "\n"; for (int i = 0; i < n; i++) if (!skip[i]) cout << a[i] << ‘ ‘; cout << "\n"; } int main() { int t; cin >> t; while (t--) solve(); }
Codeforces Round #649 (Div. 2) B. Most socially-distanced subsequence
原文：https://www.cnblogs.com/Kanoon/p/13124731.html