排序子序列

题目连接：https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int arr[N];
int ret;

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];

    int i = 0;
    while(i < n)
    {
        if(i == n - 1)
        {
            ret++;
            break;
        }
        
        if(arr[i] < arr[i + 1])
        {
            while(i < n - 1 && arr[i] <= arr[i + 1]) i++;
            ret++;
        }
        else if(arr[i] > arr[i + 1])
        {
            while(i < n - 1 && arr[i] >= arr[i + 1]) i++;
            ret++;
        }
        
        i++;
    }
    cout << ret << endl;
    return 0;
}

1. 问题本质：要将数组划分为最少的 “非递增” 或 “非递减” 子序列。由于尽可能长的延续当前趋势可以减少分段数，因此用贪心策略：一旦发现当前子序列的趋势（递增 / 递减），就尽可能往后延伸，直到趋势改变。
2. 关键观察：非递减子序列：满足 arr[i] ≤ arr[i+1]，可以一直往后找，直到出现 arr[i] > arr[i+1]。非递增子序列：满足 arr[i] ≥ arr[i+1]，可以一直往后找，直到出现 arr[i] < arr[i+1]。相等的情况：arr[i] == arr[i+1] 会被包含在当前趋势中（非递减 / 非递增都允许相等）。