请给出下题的c++参考代码For an array of integers [a1,a2,…,an], let's call the value |a1−a2|+|a2−a3|+⋯+|an−1−an| the contrast of the array. Note that the contrast of an array of size 1 is equal to 0 . You are given an array of integers a . Your task is to build an array of b in such a way that all the following conditions are met: b is not empty, i.e there is at least one element; b is a subsequence of a, i.e b can be produced by deleting some elements from a (maybe zero); the contrast of b is equal to the contrast of a . What is the minimum possible size of the array b ? Input The first line contains a single integer t (1≤t≤104 ) — the number of test cases. The first line of each test case contains a single integer n (1≤n≤3⋅105) — the size of the array a . The second line contains n integers a1,a2,⋅,an (0≤ai≤109 ) — elements of the array itself. The sum of n over all test cases doesn't exceed 3⋅105 . Output For each test case, print a single integer — the minimum possible size of the array b .

以下是参考代码，时间复杂度为O(n)：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (i > 0) {
                sum += abs(a[i] - a[i - 1]);
            }
        }
        long long max_diff = 0;
        for (int i = 1; i < n - 1; i++) {
            max_diff = max(max_diff, abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i]) - abs(a[i + 1] - a[i - 1]));
        }
        cout << sum - max_diff << endl;
    }
    return 0;
}

思路：

题目要求找到一个非空子序列，其 contrast 值等于原序列的 contrast 值，且该子序列长度最小。对于一个长度大于等于2的子序列，其 contrast 值可以拆分成相邻元素之差的绝对值之和，即

|a[i]-a[i-1]| + |a[i+1]-a[i]|

利用绝对值的性质，可以将其拆分为

(a[i]-a[i-1]) + (a[i+1]-a[i]), a[i]>a[i-1] and a[i+1]>a[i]

(a[i-1]-a[i]) + (a[i]-a[i+1]), a[i]<a[i-1] and a[i+1]<a[i]

(a[i]-a[i-1]) + (a[i]-a[i+1]), a[i]>a[i-1] and a[i+1]<a[i]

(a[i-1]-a[i]) + (a[i+1]-a[i]), a[i]<a[i-1] and a[i+1]>a[i]

其中第三种情况需要特殊处理，即对于一个数列 a，找到一个位置 i，使得 a[i-1]<a[i]>a[i+1]，将 a[i] 从子序列中删除，即可得到一个新的子序列，其 contrast 值等于原序列的 contrast 值。

因此，我们可以遍历整个序列，计算出原序列的 contrast 值。然后再遍历一遍序列，找到最大的相邻元素之差，计算出其对应的拆分方式，即可得到最小的子序列长度。