区间动态规划例题：最长湍流子数组问题（最大长度）
题目描述：
给定一个整数数组arr，如果连续子数组arr[i..j]满足：对于每个相邻元素对，比较符号在大于和小于之间交替出现，那么该子数组称为湍流子数组。更形式化地说，当索引k满足i ≤ k < j时：
- 如果k是偶数，arr[k] > arr[k+1]，且当k是奇数时，arr[k] < arr[k+1]；或者
- 如果k是偶数，arr[k] < arr[k+1]，且当k是奇数时，arr[k] > arr[k+1]
请找出arr中最长湍流子数组的长度。
解题过程：
-
问题分析：
湍流子数组要求相邻元素的比较关系交替变化。我们需要找到一个连续子数组，其中元素的大小关系按照"大-小-大-小..."或"小-大-小-大..."的模式交替排列。 -
状态定义：
定义dp[i]表示以第i个元素结尾的最长湍流子数组的长度。但这样定义不够，因为我们还需要知道当前是处于上升趋势还是下降趋势。
更好的方法是定义两个状态数组：
- up[i]: 以arr[i]结尾，且arr[i] > arr[i-1]的最长湍流子数组长度
- down[i]: 以arr[i]结尾，且arr[i] < arr[i-1]的最长湍流子数组长度
- 状态转移方程：
对于每个位置i（i ≥ 1）：
-
如果arr[i] > arr[i-1]，说明当前是上升趋势：
- up[i] = down[i-1] + 1 // 接在下降趋势后面
- down[i] = 1 // 下降趋势重置为1（只包含当前元素）
-
如果arr[i] < arr[i-1]，说明当前是下降趋势：
- down[i] = up[i-1] + 1 // 接在上升趋势后面
- up[i] = 1 // 上升趋势重置为1
-
如果arr[i] == arr[i-1]，两个趋势都重置：
- up[i] = 1
- down[i] = 1
- 初始条件：
对于第一个元素（i = 0）：
- up[0] = 1 // 单个元素可以看作长度为1的湍流子数组
- down[0] = 1
- 计算过程示例：
以arr = [9,4,2,10,7,8,8,1,9]为例：
i=0: up[0]=1, down[0]=1, max_len=1
i=1: 9>4? 否；9<4? 是 → down[1]=up[0]+1=2, up[1]=1, max_len=2
i=2: 4>2? 是 → up[2]=down[1]+1=3, down[2]=1, max_len=3
i=3: 2<10? 是 → down[3]=up[2]+1=4, up[3]=1, max_len=4
i=4: 10>7? 是 → up[4]=down[3]+1=5, down[4]=1, max_len=5
i=5: 7<8? 是 → down[5]=up[4]+1=6, up[5]=1, max_len=6
i=6: 8=8? 是 → up[6]=1, down[6]=1, max_len=6
i=7: 8>1? 是 → up[7]=down[6]+1=2, down[7]=1, max_len=6
i=8: 1<9? 是 → down[8]=up[7]+1=3, up[8]=1, max_len=6
- 空间优化：
由于每个状态只依赖于前一个状态，我们可以用变量代替数组：
- up_prev, down_prev: 前一个位置的up和down值
- up_curr, down_curr: 当前位置的up和down值
- max_len: 记录最大值
- 算法实现：
def maxTurbulenceSize(arr):
n = len(arr)
if n == 1:
return 1
up = 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 = down = 1
max_len = max(max_len, up, down)
return max_len
- 复杂度分析：
- 时间复杂度：O(n)，只需遍历数组一次
- 空间复杂度：O(1)，只使用了常数级别的额外空间
这个解法通过维护上升和下降两种状态，巧妙地捕捉了湍流子数组的交替特性，是区间动态规划思想的典型应用。