题解：最长交替子序列问题（Antimonotonicity）

一、题目分析

本题要求找出一个最长子序列，满足交替的“大于”和“小于”关系，即形如 Mary0 > Mary1 < Mary2 > Mary3 < ...。序列中的元素互不相同，因此可以通过分析相邻元素的大小关系来构造最长交替子序列。

二、代码解析

#include <stdio.h>
#include <iostream>
using namespace std;

int main() {
    int T, n, t;
    int a[30005];
    int dp[30005][4]; // dp[i][0] 表示前i个元素的最后一个关系是否为上升（0为下降，1为上升），dp[i][1]表示长度，dp[i][2]表示最后一个元素的值

    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            dp[i][1] = 1; // 初始长度为1
            dp[i][2] = a[i]; // 初始最后一个元素为自身
        }

        if (n == 1) { // 特判：单个元素时长度为1
            printf("1\n");
            continue;
        }

        // 初始化前两个元素的状态
        dp[1][0] = 0; // 第一个元素无前后关系，假设初始为下降状态（可任意设定，不影响后续）
        if (a[1] > a[2]) {
            dp[2][0] = 0; // 第二个元素与前一个形成下降关系（即Mary0 > Mary1）
            dp[2][1] = 2;
        } else {
            dp[2][0] = 1; // 第二个元素与前一个形成上升关系（但题目要求首项为下降，此处可能存在逻辑调整）
            dp[2][1] = 1; // 若前两个元素递增，则最长子序列仍为第一个元素（长度1）
        }

        for (int i = 3; i <= n; i++) {
            if (dp[i-1][0] == 0) { // 前一个关系为下降（即需要找上升）
                if (a[i] < dp[i-1][2]) { // 当前元素小于前一个元素，继续下降关系（不符合交替要求）
                    dp[i][0] = 0;
                    dp[i][1] = dp[i-1][1]; // 长度不变
                } else { // 当前元素大于前一个元素，形成上升关系（满足交替）
                    dp[i][0] = 1;
                    dp[i][1] = dp[i-1][1] + 1;
                }
            } else { // 前一个关系为上升（即需要找下降）
                if (a[i] > dp[i-1][2]) { // 当前元素大于前一个元素，继续上升关系（不符合交替要求）
                    dp[i][0] = 1;
                    dp[i][1] = dp[i-1][1]; // 长度不变
                } else { // 当前元素小于前一个元素，形成下降关系（满足交替）
                    dp[i][0] = 0;
                    dp[i][1] = dp[i-1][1] + 1;
                }
            }
            dp[i][2] = a[i]; // 更新当前最后一个元素的值
        }

        printf("%d\n", dp[n][1]);
    }
    return 0;
}

三、核心思路

1. 状态定义：

   • dp[i][0]：表示前 i 个元素构成的最长子序列的最后一个关系是否为上升（0 表示下降，1 表示上升）。
   • dp[i][1]：表示前 i 个元素构成的最长子序列的长度。
   • dp[i][2]：表示前 i 个元素构成的最长子序列的最后一个元素的值。

2. 状态转移：

   • 若前一个关系为下降（dp[i-1][0] = 0），则当前需要找上升关系（即当前元素 > 前一个元素）。
     • 若当前元素满足上升关系，长度加 1，并更新关系为上升（dp[i][0] = 1）。
     • 否则，长度不变，关系保持下降。
   • 若前一个关系为上升（dp[i-1][0] = 1），则当前需要找下降关系（即当前元素 < 前一个元素）。
     • 若当前元素满足下降关系，长度加 1，并更新关系为下降（dp[i][0] = 0）。
     • 否则，长度不变，关系保持上升。

3. 初始条件：

   • 单个元素时，长度为 1。
   • 前两个元素根据大小关系初始化：若递减则长度为 2，否则长度为 1（因为首项需为下降关系，递增时无法形成有效交替）。

四、关键点总结

• 贪心策略：通过维护当前子序列的最后一个关系（上升或下降），动态更新最长长度，避免了复杂的遍历，时间复杂度为 ( O(n) )。
• 状态简化：仅记录最后一个元素的值和关系，减少空间开销，适用于 ( n \leq 30000 ) 的数据规模。
• 边界处理：特判单个元素的情况，并正确初始化前两个元素的状态，确保后续转移逻辑正确。

该解法通过线性遍历和状态转移，高效地解决了最长交替子序列问题，满足题目要求的时间和空间复杂度。