题目分析

本题要求从原序列中选出一个最长子序列，满足波浪形（锯齿形）排列，即满足以下两种模式之一：

• 模式 0（峰谷峰谷...）：$g_{2i} > g_{2i-1}$ 且 $g_{2i} > g_{2i+1}$
• 模式 1（谷峰谷峰...）：$g_{2i} < g_{2i-1}$ 且 $g_{2i} < g_{2i+1}$

动态规划状态设计

定义状态：

• $f[i][0]$：以第 $i$ 株花结尾，且第 $i$ 株花处于下降趋势（即作为波峰）时的最长序列长度
• $f[i][1]$：以第 $i$ 株花结尾，且第 $i$ 株花处于上升趋势（即作为波谷）时的最长序列长度

状态转移方程：

• 如果 $a[i-1] < a[i]$（当前比前一个高）：
  • 可以接在下降趋势后面形成新的上升趋势：$f[i][1] = f[i-1][1]$
  • 也可以接在上升趋势后面形成转折：$f[i][0] = \max(f[i-1][0], f[i-1][1] + 1)$
• 如果 $a[i-1] > a[i]$（当前比前一个低）：
  • 可以接在上升趋势后面形成新的下降趋势：$f[i][0] = f[i-1][0]$
  • 也可以接在下降趋势后面形成转折：$f[i][1] = \max(f[i-1][1], f[i-1][0] + 1)$
• 如果 $a[i-1] = a[i]$（高度相等）：
  • 保持原有趋势：$f[i][0] = f[i-1][0], f[i][1] = f[i-1][1]$

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int a[N], f[N][2];
int n;

int main() {
    cin >> n;
    
    // 读入花的高度序列
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    // 初始化：第一株花两种模式都可以，长度为1
    f[1][0] = f[1][1] = 1;
    
    // 动态规划递推
    for (int i = 2; i <= n; i++) {
        if (a[i - 1] < a[i]) {
            // 当前比前一个高
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + 1);
            f[i][1] = f[i - 1][1];
        } else if (a[i - 1] > a[i]) {
            // 当前比前一个低
            f[i][1] = max(f[i - 1][1], f[i - 1][0] + 1);
            f[i][0] = f[i - 1][0];
        } else {
            // 高度相等，保持原状
            f[i][0] = f[i - 1][0];
            f[i][1] = f[i - 1][1];
        }
    }
    
    // 输出两种模式的最大值
    cout << max(f[n][1], f[n][0]);
    return 0;
}

算法流程

1. 初始化：第一株花单独构成序列，两种模式长度均为 $1$
2. 状态转移：从第 $2$ 株到第 $n$ 株花，根据与前一朵花的高度关系更新状态
3. 结果输出：取两种模式的最大值作为答案

复杂度分析

• 时间复杂度：$O(n)$
  只需一次线性扫描
• 空间复杂度：$O(n)$
  使用两个 $n$ 大小的 DP 数组

示例验证

样例输入：

n = 5
a = [5, 3, 2, 1, 2]

计算过程：

• $i=1$：$f[1][0]=1, f[1][1]=1$
• $i=2$：$5>3$，下降趋势
  $f[2][1] = \max(1, 1+1) = 2$，$f[2][0] = 1$
• $i=3$：$3>2$，下降趋势
  $f[3][1] = \max(2, 1+1) = 2$，$f[3][0] = 1$
• $i=4$：$2>1$，下降趋势
  $f[4][1] = \max(2, 1+1) = 2$，$f[4][0] = 1$
• $i=5$：$1<2$，上升趋势
  $f[5][0] = \max(1, 2+1) = 3$，$f[5][1] = 2$

输出：$\max(3, 2) = 3$，与样例一致。

算法优势

• 高效性：线性时间复杂度，适用于 $n \leq 2 \times 10^6$ 的大数据范围
• 简洁性：状态设计清晰，转移逻辑简单
• 正确性：覆盖所有可能的情况，保证找到最优解

该动态规划解法充分利用了波浪序列的局部性质，通过比较相邻元素的高度关系进行状态转移，是本题的最优解法。