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

让我为您讲解一个有趣的线性动态规划问题——最长湍流子数组。

问题描述

给定一个整数数组 arr，如果某个子数组满足比较符号在相邻元素之间来回翻转，则称这个子数组为"湍流子数组"。更形式化地说：

• 当 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 = [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]：以第 i 个元素结尾，且最后是上升趋势（arr[i-1] < arr[i]）的最长湍流子数组长度
• down[i]：以第 i 个元素结尾，且最后是下降趋势（arr[i-1] > arr[i]）的最长湍流子数组长度

步骤3：状态转移方程

对于每个位置 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：边界条件

• 当数组只有一个元素时，湍流子数组长度为1
• 初始状态：up[0] = 1, down[0] = 1

步骤5：算法实现

def maxTurbulenceSize(arr):
    n = len(arr)
    if n == 1:
        return 1
    
    up = [1] * n  # 以i结尾，最后是上升趋势的最长湍流子数组长度
    down = [1] * n  # 以i结尾，最后是下降趋势的最长湍流子数组长度
    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：空间优化

由于我们只需要前一个状态，可以进行空间优化：

def maxTurbulenceSize_optimized(arr):
    n = len(arr)
    if n == 1:
        return 1
    
    up = 1  # 当前上升趋势的长度
    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 = 1
            down = 1
        
        max_len = max(max_len, up, down)
    
    return max_len

示例分析

以 arr = [9,4,2,10,7,8,8,1,9] 为例：

索引: 0  1  2  3  4  5  6  7  8
数值: 9  4  2  10 7  8  8  1  9

i=1: 9>4, down=2, up=1, max=2
i=2: 4>2, down=3, up=1, max=3  
i=3: 2<10, up=4, down=1, max=4
i=4: 10>7, down=5, up=1, max=5
i=5: 7<8, up=6, down=1, max=6
i=6: 8=8, up=1, down=1, max=6
i=7: 8>1, down=2, up=1, max=6
i=8: 1<9, up=3, down=1, max=6

最终结果是5，对应子数组 [4,2,10,7,8]。

复杂度分析

• 时间复杂度：O(n)，只需要遍历数组一次
• 空间复杂度：
  • 未优化版本：O(n)
  • 优化版本：O(1)

这个问题的关键在于理解湍流的交替特性，并通过两个状态来分别跟踪上升和下降趋势的长度。