区间动态规划例题：最长湍流子数组问题（相邻元素差正负交替的最大长度）

让我为你详细讲解这个区间动态规划问题。

问题描述
给定一个整数数组arr，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。更形式化地说，当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

解题思路

这个问题可以用区间动态规划来解决。我们需要定义状态来表示以某个位置结尾的湍流子数组的长度。

状态定义
定义两个状态数组：

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

状态转移方程

1. 基本情况：

   • 对于单个元素，up[0] = 1, down[0] = 1
   • 因为单个元素本身就是一个湍流子数组

2. 状态转移：

   • 如果arr[i] > arr[i-1]:

     • up[i] = down[i-1] + 1 // 当前上升，接在之前的下降后面
     • down[i] = 1 // 不能接在下降后面，重新开始

   • 如果arr[i] < arr[i-1]:

     • down[i] = up[i-1] + 1 // 当前下降，接在之前的上升后面
     • up[i] = 1 // 不能接在上升后面，重新开始

   • 如果arr[i] == arr[i-1]:

     • up[i] = 1, down[i] = 1 // 相等时重新开始

详细解题步骤

让我们用示例arr = [9,4,2,10,7,8,8,1,9]来演示：

步骤1：初始化

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

步骤2：逐个处理元素

i=1: arr[1]=4, arr[0]=9

• 4 < 9 ⇒ down[1] = up[0] + 1 = 2, up[1] = 1
• max_len = max(1, 2) = 2

i=2: arr[2]=2, arr[1]=4

• 2 < 4 ⇒ down[2] = up[1] + 1 = 2, up[2] = 1
• max_len = max(2, 2) = 2

i=3: arr[3]=10, arr[2]=2

• 10 > 2 ⇒ up[3] = down[2] + 1 = 3, down[3] = 1
• max_len = max(2, 3) = 3

i=4: arr[4]=7, arr[3]=10

• 7 < 10 ⇒ down[4] = up[3] + 1 = 4, up[4] = 1
• max_len = max(3, 4) = 4

i=5: arr[5]=8, arr[4]=7

• 8 > 7 ⇒ up[5] = down[4] + 1 = 5, down[5] = 1
• max_len = max(4, 5) = 5

i=6: arr[6]=8, arr[5]=8

• 8 == 8 ⇒ up[6] = 1, down[6] = 1
• max_len保持5

i=7: arr[7]=1, arr[6]=8

• 1 < 8 ⇒ down[7] = up[6] + 1 = 2, up[7] = 1
• max_len保持5

i=8: arr[8]=9, arr[7]=1

• 9 > 1 ⇒ up[8] = down[7] + 1 = 3, down[8] = 1
• max_len保持5

最终结果：最长湍流子数组长度为5

算法实现

def maxTurbulenceSize(arr):
    if not arr:
        return 0
    
    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:  # arr[i] == arr[i-1]
            up[i] = 1
            down[i] = 1
        
        max_len = max(max_len, up[i], down[i])
    
    return max_len

复杂度分析

• 时间复杂度：O(n)，只需要遍历数组一次
• 空间复杂度：O(n)，使用了两个长度为n的数组

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