def maxTurbulenceSize(arr):
    n = len(arr)
    if n == 1:
        return 1
    up = down = 1
    res = 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
        res = max(res, up, down)
    return res

区间动态规划例题：最长湍流子数组问题 题目描述 给定一个整数数组 arr ，如果某个子数组满足相邻元素的比较符号在“大于”和“小于”之间交替出现（例如 arr[k-1] < arr[k] > arr[k+1] 或 arr[k-1] > arr[k] < arr[k+1] ），则称该子数组为“湍流子数组”。要求返回最长的湍流子数组的长度。 示例 输入： arr = [9,4,2,10,7,8,8,1,9] 输出： 5 解释：最长的湍流子数组为 [4,2,10,7,8] ，其比较关系为 4 > 2 < 10 > 7 < 8 。 解题思路 问题分析 湍流子数组要求相邻元素的大小关系交替变化（ < 和 > 交替）。 若子数组长度为 1，默认满足湍流条件（长度为 1）。 本题可通过动态规划记录以每个位置结尾的最长湍流子数组长度。 状态定义 定义两个状态数组： up[i] ：以 arr[i] 结尾，且 arr[i] > arr[i-1] 的最长湍流子数组长度。 down[i] ：以 arr[i] 结尾，且 arr[i] < arr[i-1] 的最长湍流子数组长度。 状态转移 若 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] = down[i] = 1 （相等时趋势中断，只能以当前元素重新开始）。 初始条件 当 i=0 （首个元素）时， up[0] = down[0] = 1 。 结果提取 遍历所有位置，取 max(up[i], down[i]) 的最大值。 详细推导过程 以示例 arr = [9,4,2,10,7,8,8,1,9] 为例： | i | arr[ i] | 与前一元素关系 | up[ i] | down[ i ] | 说明 | |---|--------|---------------|-------|---------|------| | 0 | 9 | - | 1 | 1 | 初始状态 | | 1 | 4 | < | 1 | 2 | 下降趋势延续： down[1]=up[0]+1=2 | | 2 | 2 | < | 1 | 1 | 连续下降中断，重置为 1 | | 3 | 10 | > | 2 | 1 | 上升趋势： up[3]=down[2]+1=2 | | 4 | 7 | < | 1 | 3 | 下降趋势： down[4]=up[3]+1=3 | | 5 | 8 | > | 4 | 1 | 上升趋势： up[5]=down[4]+1=4 | | 6 | 8 | = | 1 | 1 | 相等中断趋势 | | 7 | 1 | < | 1 | 2 | 下降趋势： down[7]=up[6]+1=2 | | 8 | 9 | > | 3 | 1 | 上升趋势： up[8]=down[7]+1=3 | 最大值出现在 i=5 时， max(up[5], down[5]) = 4 ，但实际最长湍流子数组为 [4,2,10,7,8] （长度为 5）。 注意 ：表中 i=5 对应子数组结束位置为索引 5（元素 8），但实际湍流子数组从索引 1（元素 4）开始，长度为 5。 修正： up[i] 和 down[i] 记录的长度已包含起始位置，因此最终结果正确为 5（需检查索引范围）。 算法优化 只需前一个状态，可优化空间复杂度为 O(1)。 遍历时直接比较 arr[i] 与 arr[i-1] ，更新当前 up 和 down 值。 代码实现（简化版）