区间动态规划例题：最长湍流子数组问题（进阶版）

字数 2243 2025-11-03 08:34:44

区间动态规划例题：最长湍流子数组问题（进阶版）

题目描述
给定一个整数数组 arr，如果连续子数组 arr[i...j] 满足以下条件之一，则称为湍流子数组：

对于所有索引 k（i ≤ k < j），当 k 为奇数时 arr[k] > arr[k+1]，当 k 为偶数时 arr[k] < arr[k+1]；
对于所有索引 k（i ≤ k < j），当 k 为奇数时 arr[k] < arr[k+1]，当 k 为偶数时 arr[k] > arr[k+1]。

注意：这里的奇偶性指的是子数组内的相对位置（即 k-i 的奇偶性），而非原数组索引的奇偶性。
请找出最长的湍流子数组的长度。

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

索引0（值4）到索引1（值2）：4>2（偶数位置下降）
索引1（值2）到索引2（值10）：2<10（奇数位置上升）
索引2（值10）到索引3（值7）：10>7（偶数位置下降）
索引3（值7）到索引4（值8）：7<8（奇数位置上升）

解题思路（区间动态规划）

状态定义
定义 dp[i][j] 表示子数组 arr[i...j] 是否为湍流子数组（1表示是，0表示否）。
但直接二维DP会超时（O(n²)），需优化。
优化状态设计
观察发现，湍流条件仅依赖相邻元素的比较结果。我们可以用两个一维数组：
- up[i]：以 i 结尾，且最后一段是上升（即 arr[i-1] < arr[i]）的最长湍流子数组长度。
- down[i]：以 i 结尾，且最后一段是下降（即 arr[i-1] > arr[i]）的最长湍流子数组长度。
状态转移
- 如果 arr[i-1] < arr[i]：
  - 当前上升段可接在之前的下降段后：up[i] = down[i-1] + 1
  - 下降段中断：down[i] = 1（单独一个元素视为长度为1的湍流子数组）
- 如果 arr[i-1] > arr[i]：
  - 当前下降段可接在之前的上升段后：down[i] = up[i-1] + 1
  - 上升段中断：up[i] = 1
- 如果 arr[i-1] == arr[i]：
  - 上升和下降均中断：up[i] = down[i] = 1
初始化
- 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	9>4（下降）	1	up[0]+1=2	down[1]继承上升段
2	2	4>2（下降）	down[1]+1=3	1	连续下降？注意相对位置：索引1（值4→2）是下降（偶数位），索引2（值2→10）需上升，但此时比较的是2和10，需看下一步
3	10	2<10（上升）	down[2]+1=2	up[2]+1=4？错误！需重新检查转移逻辑

修正转移逻辑
实际规则应基于相对位置的奇偶性交替。但上述简化方法等价于：

若当前比较方向与上一次相反，则长度+1；否则重置为2（若相等则重置为1）。

正确计算：

i=0: up=1, down=1
i=1: 9>4 → down[1]=up[0]+1=2, up[1]=1
i=2: 4>2 → 当前下降，但前一次也是下降（9>4），不满足交替，因此 down[2]=2（从4开始的新下降段），up[2]=1
i=3: 2<10 → 上升，前一次是下降（4>2），满足交替：up[3]=down[2]+1=3, down[3]=1
i=4: 10>7 → 下降，前一次是上升（2<10），满足交替：down[4]=up[3]+1=4, up[4]=1
i=5: 7<8 → 上升，前一次是下降（10>7），满足交替：up[5]=down[4]+1=5, down[5]=1
i=6: 8==8 → 相等：up[6]=1, down[6]=1
i=7: 8>1 → 下降：down[7]=up[6]+1=2, up[7]=1
i=8: 1<9 → 上升：up[8]=down[7]+1=3, down[8]=1

最大值在 i=5 时取到 max(up[5],down[5])=5，对应子数组 [4,2,10,7,8]。

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)（可优化到O(1)）

关键点
湍流子数组的本质是相邻比较符号交替出现，区间DP通过状态机（上升/下降）避免二维枚举，直接线性扫描即可求解。

区间动态规划例题：最长湍流子数组问题（进阶版）题目描述给定一个整数数组 arr ，如果连续子数组 arr[i...j] 满足以下条件之一，则称为湍流子数组：对于所有索引 k （ i ≤ k < j ），当 k 为奇数时 arr[k] > arr[k+1] ，当 k 为偶数时 arr[k] < arr[k+1] ；对于所有索引 k （ i ≤ k < j ），当 k 为奇数时 arr[k] < arr[k+1] ，当 k 为偶数时 arr[k] > arr[k+1] 。注意：这里的奇偶性指的是子数组内的相对位置（即 k-i 的奇偶性），而非原数组索引的奇偶性。请找出最长的湍流子数组的长度。示例输入： arr = [9,4,2,10,7,8,8,1,9] 输出： 5 解释：最长的湍流子数组是 [4,2,10,7,8] ，其中相对位置满足：索引0（值4）到索引1（值2）：4>2（偶数位置下降）索引1（值2）到索引2（值10）：2 <10（奇数位置上升）索引2（值10）到索引3（值7）：10>7（偶数位置下降）索引3（值7）到索引4（值8）：7 <8（奇数位置上升）解题思路（区间动态规划）状态定义定义 dp[i][j] 表示子数组 arr[i...j] 是否为湍流子数组（1表示是，0表示否）。但直接二维DP会超时（O(n²)），需优化。优化状态设计观察发现，湍流条件仅依赖相邻元素的比较结果。我们可以用两个一维数组： up[i] ：以 i 结尾，且最后一段是上升（即 arr[i-1] < arr[i] ）的最长湍流子数组长度。 down[i] ：以 i 结尾，且最后一段是下降（即 arr[i-1] > arr[i] ）的最长湍流子数组长度。状态转移如果 arr[i-1] < arr[i] ：当前上升段可接在之前的下降段后： up[i] = down[i-1] + 1 下降段中断： down[i] = 1 （单独一个元素视为长度为1的湍流子数组）如果 arr[i-1] > arr[i] ：当前下降段可接在之前的上升段后： down[i] = up[i-1] + 1 上升段中断： up[i] = 1 如果 arr[i-1] == arr[i] ：上升和下降均中断： up[i] = down[i] = 1 初始化 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 | 9>4（下降） | 1 | up[ 0]+1=2 | down[ 1 ]继承上升段 | | 2 | 2 | 4>2（下降） | down[ 1 ]+1=3 | 1 | 连续下降？注意相对位置：索引1（值4→2）是下降（偶数位），索引2（值2→10）需上升，但此时比较的是2和10，需看下一步 | | 3 | 10 | 2<10（上升） | down[ 2]+1=2 | up[ 2 ]+1=4？错误！需重新检查转移逻辑 | 修正转移逻辑实际规则应基于相对位置的奇偶性交替。但上述简化方法等价于：若当前比较方向与上一次相反，则长度+1；否则重置为2（若相等则重置为1）。正确计算： i=0: up=1, down=1 i=1: 9>4 → down[ 1]=up[ 0]+1=2, up[ 1 ]=1 i=2: 4>2 → 当前下降，但前一次也是下降（9>4），不满足交替，因此 down[ 2]=2（从4开始的新下降段），up[ 2 ]=1 i=3: 2<10 → 上升，前一次是下降（4>2），满足交替：up[ 3]=down[ 2]+1=3, down[ 3 ]=1 i=4: 10>7 → 下降，前一次是上升（2<10），满足交替：down[ 4]=up[ 3]+1=4, up[ 4 ]=1 i=5: 7<8 → 上升，前一次是下降（10>7），满足交替：up[ 5]=down[ 4]+1=5, down[ 5 ]=1 i=6: 8==8 → 相等：up[ 6]=1, down[ 6 ]=1 i=7: 8>1 → 下降：down[ 7]=up[ 6]+1=2, up[ 7 ]=1 i=8: 1<9 → 上升：up[ 8]=down[ 7]+1=3, down[ 8 ]=1 最大值在 i=5 时取到 max(up[5],down[5])=5 ，对应子数组 [4,2,10,7,8] 。复杂度分析时间复杂度：O(n) 空间复杂度：O(n)（可优化到O(1)）关键点湍流子数组的本质是相邻比较符号交替出现，区间DP通过状态机（上升/下降）避免二维枚举，直接线性扫描即可求解。