区间动态规划例题：最长湍流子数组问题 题目描述： 给定一个整数数组 arr，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组为湍流子数组。更正式地说，对于子数组 arr[ i...j ]： 当 i <= k < j 时： 如果 k 是偶数，arr[ k] > arr[ k+1 ] 如果 k 是奇数，arr[ k] < arr[ k+1 ] 或者： 当 i <= k < j 时： 如果 k 是偶数，arr[ k] < arr[ k+1 ] 如果 k 是奇数，arr[ k] > arr[ k+1 ] 请返回 arr 中最长湍流子数组的长度。 解题过程： 问题分析： 湍流子数组要求相邻元素的比较关系交替变化（大于/小于交替出现）。我们需要找到最长的连续子数组满足这个条件。 状态定义： 定义两个状态数组： up[ i]：以第 i 个元素结尾，且最后一段是上升（arr[ i-1] < arr[ i ]）的最长湍流子数组长度 down[ i]：以第 i 个元素结尾，且最后一段是下降（arr[ i-1] > arr[ i ]）的最长湍流子数组长度 状态转移方程： 对于 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] = 1，down[ i ] = 1 边界条件： 当 i = 0 时，单个元素本身就是一个湍流子数组，长度为 1。 算法步骤： 初始化 up[ 0] = 1，down[ 0 ] = 1 初始化最大长度 max_ len = 1 遍历数组 i 从 1 到 n-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 ] = 1 down[ i ] = 1 更新 max_ len = max(max_ len, up[ i], down[ i ]) 返回 max_ len 示例演示： 以 arr = [ 9,4,2,10,7,8,8,1,9 ] 为例： i=0：up=1，down=1，max_ len=1 i=1：4<9，down=2，up=1，max_ len=2 i=2：2<4，down=up[ 1]+1=2，max_ len=2 i=3：10>2，up=down[ 2]+1=3，max_ len=3 i=4：7<10，down=up[ 3]+1=4，max_ len=4 i=5：8>7，up=down[ 4]+1=5，max_ len=5 i=6：8=8，重置为1，max_ len=5 i=7：1<8，down=up[ 6]+1=2，max_ len=5 i=8：9>1，up=down[ 7]+1=3，max_ len=5 最终结果为 5，对应子数组 [ 4,2,10,7,8 ]。