最长湍流子数组问题（最大长度）

题目描述

给定一个整数数组 arr，如果连续子数组满足以下条件，就称之为湍流子数组：

• 相邻元素的大小关系在“大于”和“小于”之间交替变化。
• 更形式化地，如果比较符号在子数组中每对相邻元素之间翻转，则该子数组是湍流子数组。

具体来说：

• 对于子数组 arr[i…j]，如果满足：
  • 当 i 是奇数时，arr[k] > arr[k+1] 且当 i 是偶数时，arr[k] < arr[k+1]；
  • 或者当 i 是奇数时，arr[k] < arr[k+1] 且当 i 是偶数时，arr[k] > arr[k+1]。
• 但更直观的理解是：比较符号（大于、小于）在相邻对之间交替变化。

注意：

• 长度为 1 的子数组视为湍流子数组。
• 如果长度为 2，则要求两个元素不相等（否则没有交替的比较关系）。

目标：返回 arr 中最长湍流子数组的长度。

示例 1：

输入: arr = [9,4,2,10,7,8,8,1,9]
输出: 5
解释: 最长湍流子数组是 [4,2,10,7,8]，对应的比较序列是：>、<、>、<。

示例 2：

输入: arr = [4,8,12,16]
输出: 2
解释: 最长湍流子数组可以是 [4,8] 或 [8,12] 或 [12,16]。

为什么可以用区间动态规划？

这个问题本质是求最长满足某种性质的连续子数组，通常可以用滑动窗口或动态规划解决。
但“湍流”性质涉及相邻元素的比较，如果从“区间”的角度思考，可以定义状态表示某个区间是否为湍流子数组，但这样复杂度较高（O(n²)）。
不过，我们可以用一维动态规划更高效地解决，但为了符合“区间DP”的要求，这里我们先用朴素区间DP思路分析，再给出优化。

解题思路（区间DP）

步骤 1：定义状态

设 dp[i][j] 表示子数组 arr[i…j] 是否是湍流子数组（布尔值）。

• 如果 dp[i][j] = true，则 arr[i…j] 满足湍流性质。
• 目标是找到所有满足条件的区间中，j - i + 1 的最大值。

步骤 2：状态转移

湍流性质是相邻比较符号交替，我们可以从较短的区间递推到较长的区间。
考虑区间 [i, j]，如果已知 [i, j-1] 是湍流子数组，那么只需检查最后两个元素 arr[j-1] 和 arr[j] 的比较关系是否与前一个比较符号相反即可。

但这样需要知道前一个比较符号的方向。
为了在状态中记录方向，我们可以将状态扩充为：
dp[i][j][0] 表示 arr[i…j] 是湍流子数组，且最后一步是比较符号是“上升”（即 arr[j-1] < arr[j]）。
dp[i][j][1] 表示 arr[i…j] 是湍流子数组，且最后一步是比较符号是“下降”（即 arr[j-1] > arr[j]）。

初始化：

• 对于长度为 1 的区间：dp[i][i][0] = dp[i][i][1] = true（单个元素总是湍流，但注意长度为 1 时没有“最后一步”的比较，所以实际上我们只关心长度 ≥ 2 的情况）。
• 长度为 2 的区间：
  • 如果 arr[i] < arr[i+1]，则 dp[i][i+1][0] = true。
  • 如果 arr[i] > arr[i+1]，则 dp[i][i+1][1] = true。

状态转移（j > i+1）：

• 如果 arr[j-1] < arr[j] 且 dp[i][j-1][1] = true（前一步是下降，这一步上升，则交替），则 dp[i][j][0] = true。
• 如果 arr[j-1] > arr[j] 且 dp[i][j-1][0] = true（前一步是上升，这一步下降，则交替），则 dp[i][j][1] = true。

步骤 3：计算最长长度

遍历所有 i, j，如果 dp[i][j][0] 或 dp[i][j][1] 为 true，则更新最大长度为 j - i + 1。

复杂度：状态数 O(n²)，转移 O(1)，总 O(n²)。

优化到一维 DP

实际上，这个问题有更简单的 O(n) 解法，但既然我们重点讲区间DP，先给出区间DP代码框架，再简要提优化。

区间DP伪代码：

n = len(arr)
dp0 = [[False]*n for _ in range(n)]  # 最后上升
dp1 = [[False]*n for _ in range(n)]  # 最后下降
ans = 1
# 长度 1
for i in range(n):
    dp0[i][i] = dp1[i][i] = True
# 长度 2
for i in range(n-1):
    if arr[i] < arr[i+1]:
        dp0[i][i+1] = True
        ans = 2
    elif arr[i] > arr[i+1]:
        dp1[i][i+1] = True
        ans = 2
# 长度 ≥ 3
for length in range(3, n+1):
    for i in range(n - length + 1):
        j = i + length - 1
        if arr[j-1] < arr[j] and dp1[i][j-1]:
            dp0[i][j] = True
            ans = length
        if arr[j-1] > arr[j] and dp0[i][j-1]:
            dp1[i][j] = True
            ans = length
return ans

更优解法（滑动窗口 / 一维DP）

由于湍流性质只依赖于相邻对，我们可以用两个一维数组：

• up[i]：以 i 结尾，且最后一步是上升（arr[i-1] < arr[i]）的最长湍流子数组长度。
• down[i]：以 i 结尾，且最后一步是下降（arr[i-1] > arr[i]）的最长湍流子数组长度。

转移：

• 如果 arr[i-1] < arr[i]，则 up[i] = down[i-1] + 1，down[i] = 1。
• 如果 arr[i-1] > arr[i]，则 down[i] = up[i-1] + 1，up[i] = 1。
• 如果相等，则 up[i] = down[i] = 1。

初始化：up[0] = down[0] = 1。
答案：max(up[i], down[i]) 的最大值。

复杂度：O(n) 时间，O(1) 空间（可优化到只存前一个状态）。

总结

1. 区间DP思路：定义 dp[i][j][0/1] 表示区间是否为湍流子数组，并记录最后比较方向，从短区间递推长区间。
2. 状态转移：根据最后两个元素的比较符号与前一个区间的方向是否交替，更新当前区间状态。
3. 计算答案：所有满足条件的区间长度的最大值。
4. 优化：由于湍流性质是“局部”依赖，可用一维DP或滑动窗口达到 O(n) 时间。

这样，我们从区间DP的完整思路出发，逐步推导到更优解法，确保对“湍流”性质的理解透彻。