Most socially-distanced subsequence (Codeforces 1364B)
Tags: Greedy, two pointers

Given a permutation $$$p$$$ of length $$$n$$$, find its subsequence $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_k$$$ of length at least $$$2$$$ such that:  $$$|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$$$ 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.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of the permutation $$$p$$$.The second line of each test case contains $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_{n}$$$ ($$$1 \le p_i \le n$$$, $$$p_i$$$ are distinct) — the elements of the permutation $$$p$$$.The sum of $$$n$$$ across the test cases doesn't exceed $$$10^5$$$.

Output: For each test case, the first line should contain the length of the found subsequence, $$$k$$$. The second line should contain $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_k$$$ — its elements.If multiple subsequences satisfy these conditions, you are allowed to find any of them.

Note: In the first test case, there are $$$4$$$ subsequences of length at least $$$2$$$:  $$$[3,2]$$$ which gives us $$$|3-2|=1$$$.  $$$[3,1]$$$ which gives us $$$|3-1|=2$$$.  $$$[2,1]$$$ which gives us $$$|2-1|=1$$$.  $$$[3,2,1]$$$ which gives us $$$|3-2|+|2-1|=2$$$. So the answer is either $$$[3,1]$$$ or $$$[3,2,1]$$$. Since we want the subsequence to be as short as possible, the answer is $$$[3,1]$$$.

Sample Inputs:
2
3
3 2 1
4
1 3 4 2

Sample Outputs:
2
3 1 
3
1 4 2

Solution (Python):
import sys
input = sys.stdin.readline

def s():
    n = input()
    a = [int(i) for i in input().split()]
    (cr, de, res) = (a[0] < a[1], a[0] > a[1], [a[0]])
    be = a[0]
    for k in a[1:]:
        if k > be:
            if cr:
                be = k
                continue
            if de:
                res += [be]
                be = k
                (cr, de) = (True, False)
        else:
            if de:
                be = k
                continue
            if cr:
                res += [be]
                be = k
                (cr, de) = (False, True)
    res += [be]
    return res
t = int(input())
res = ''
for j in range(t):
    x = s()
    res += str(len(x)) + '\n'
    res += ' '.join([str(elem) for elem in x]) + '\n'
print(res)

Solution (Python):
from sys import stdin

def main():
    for s in stdin.read().splitlines()[2::2]:
        (a, b, *l) = map(int, s.split())
        (res, u) = ([a, b], a < b)
        for c in l:
            v = b < c
            if u is v:
                res[-1] = c
            else:
                res.append(c)
            (b, u) = (c, v)
        print(len(res), ' '.join(map(str, res)), sep='\n')
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def answer(n, p):
    ans = [p[0]]
    if p[1] > p[0]:
        asc = True
    else:
        asc = False
    for i in range(1, n):
        if asc and p[i - 1] > p[i]:
            asc = False
            ans.append(p[i - 1])
        elif not asc and p[i - 1] < p[i]:
            asc = True
            ans.append(p[i - 1])
    ans.append(p[-1])
    print(len(ans))
    print(' '.join(map(str, ans)))
    return

def main():
    t = int(input())
    while t:
        n = int(sys.stdin.readline())
        p = [int(i) for i in sys.stdin.readline().split()]
        answer(n, p)
        t -= 1
    return
main()