线性动态规划：最长湍流子数组

题目描述
给定一个整数数组arr，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组为湍流子数组。更正式地，对于子数组arr[i...j]：

• 当i为奇数时，arr[i] > arr[i+1]，且当i为偶数时，arr[i] < arr[i+1]；或者
• 当i为奇数时，arr[i] < arr[i+1]，且当i为偶数时，arr[i] > arr[i+1]

换句话说，如果相邻元素之间的比较符号（>或<）在每个相邻元素对之间翻转，则该子数组是湍流的。

请返回arr中最长湍流子数组的长度。

示例
输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：最长的湍流子数组是[4,2,10,7,8]，其中：
4 > 2, 2 < 10, 10 > 7, 7 < 8

解题过程

步骤1：理解问题本质
湍流子数组要求相邻元素的大小关系交替变化。对于任意三个连续元素arr[i-1], arr[i], arr[i+1]，必须满足：

• 要么arr[i-1] < arr[i] > arr[i+1]（形成山峰）
• 要么arr[i-1] > arr[i] < arr[i+1]（形成山谷）

步骤2：定义状态
我们可以定义两个状态数组：

• up[i]: 以arr[i]结尾，且arr[i] > arr[i-1]的最长湍流子数组长度
• down[i]: 以arr[i]结尾，且arr[i] < arr[i-1]的最长湍流子数组长度

步骤3：状态转移方程
对于每个位置i（i ≥ 1）：

1. 如果arr[i] > arr[i-1]：

   • up[i] = down[i-1] + 1 // 前一个应该是下降，现在上升
   • down[i] = 1 // 重置下降序列

2. 如果arr[i] < arr[i-1]：

   • down[i] = up[i-1] + 1 // 前一个应该是上升，现在下降
   • up[i] = 1 // 重置上升序列

3. 如果arr[i] == arr[i-1]：

   • up[i] = 1
   • down[i] = 1

步骤4：初始条件
对于第一个元素：

• up[0] = 1
• down[0] = 1

步骤5：算法实现

def maxTurbulenceSize(arr):
    n = len(arr)
    if n == 1:
        return 1
    
    up = [1] * n
    down = [1] * n
    max_len = 1
    
    for i in range(1, n):
        if arr[i] > arr[i-1]:
            up[i] = down[i-1] + 1
            down[i] = 1
        elif arr[i] < arr[i-1]:
            down[i] = up[i-1] + 1
            up[i] = 1
        else:
            up[i] = 1
            down[i] = 1
        
        max_len = max(max_len, up[i], down[i])
    
    return max_len

步骤6：详细示例分析
以arr = [9,4,2,10,7,8,8,1,9]为例：

i=1: 4<9 → down[1]=up[0]+1=2, up[1]=1
i=2: 2<4 → down[2]=up[1]+1=2, up[2]=1
i=3: 10>2 → up[3]=down[2]+1=3, down[3]=1
i=4: 7<10 → down[4]=up[3]+1=4, up[4]=1
i=5: 8>7 → up[5]=down[4]+1=5, down[5]=1
i=6: 8=8 → up[6]=1, down[6]=1
i=7: 1<8 → down[7]=up[6]+1=2, up[7]=1
i=8: 9>1 → up[8]=down[7]+1=3, down[8]=1

最长湍流子数组长度为5。

步骤7：优化空间复杂度
由于每个状态只依赖于前一个状态，我们可以用变量代替数组：

def maxTurbulenceSize(arr):
    n = len(arr)
    if n == 1:
        return 1
    
    up = down = 1
    max_len = 1
    
    for i in range(1, n):
        if arr[i] > arr[i-1]:
            up = down + 1
            down = 1
        elif arr[i] < arr[i-1]:
            down = up + 1
            up = 1
        else:
            up = down = 1
        
        max_len = max(max_len, up, down)
    
    return max_len

复杂度分析

• 时间复杂度：O(n)，只需遍历数组一次
• 空间复杂度：O(1)，只使用常数个额外变量

这种方法通过动态规划巧妙地捕捉了湍流子数组的交替特性，是解决此类问题的经典思路。