区间动态规划例题：合唱队形问题（最长递增递减子序列）
字数 1677 2025-11-06 22:52:24
区间动态规划例题：合唱队形问题（最长递增递减子序列）
题目描述：
有n个学生站成一排，每个学生有一个身高h[i]。现在需要从中选出一些学生组成合唱队形，要求队形满足：存在一个中间学生，其左边的所有学生身高严格递增，右边的所有学生身高严格递减。求最多能选出多少学生组成合唱队形。
解题过程：
- 问题分析：
- 合唱队形实际上是一个"先递增后递减"的序列
- 对于每个位置i，我们需要计算：
- 以i结尾的最长递增子序列长度（从左往右）
- 以i开头的最长递减子序列长度（从右往左）
- 然后找到使两者之和最大的位置i
- 状态定义：
定义两个数组：
- left[i]：以第i个学生结尾的最长递增子序列长度
- right[i]：以第i个学生开头的最长递减子序列长度
- 状态转移方程：
对于left数组（从左往右计算）：
left[i] = max{left[j]} + 1，其中0 ≤ j < i 且 h[j] < h[i]
如果不存在这样的j，则left[i] = 1
对于right数组（从右往左计算）：
right[i] = max{right[k]} + 1，其中i < k < n 且 h[i] > h[k]
如果不存在这样的k，则right[i] = 1
- 具体计算步骤：
步骤1：计算left数组
- 初始化left[0] = 1
- 对于i从1到n-1：
- 设置left[i] = 1
- 对于j从0到i-1：
- 如果h[j] < h[i]且left[j] + 1 > left[i]：
- left[i] = left[j] + 1
- 如果h[j] < h[i]且left[j] + 1 > left[i]：
步骤2：计算right数组
- 初始化right[n-1] = 1
- 对于i从n-2到0：
- 设置right[i] = 1
- 对于k从i+1到n-1：
- 如果h[i] > h[k]且right[k] + 1 > right[i]：
- right[i] = right[k] + 1
- 如果h[i] > h[k]且right[k] + 1 > right[i]：
步骤4：计算最大队形长度
- max_len = 0
- 对于每个位置i：
- 队形长度 = left[i] + right[i] - 1（因为位置i被计算了两次）
- max_len = max(max_len, 队形长度)
- 示例演示：
假设身高序列为：[1, 3, 2, 4, 1]
计算left数组：
- i=0: left[0]=1
- i=1: 比较h[0]=1<h[1]=3 → left[1]=left[0]+1=2
- i=2: 比较h[0]=1<h[2]=2 → left[2]=2
- i=3: 比较前三个 → left[3]=max(left[0],left[1],left[2])+1=3
- i=4: 无满足条件的j → left[4]=1
left = [1, 2, 2, 3, 1]
计算right数组：
- i=4: right[4]=1
- i=3: 比较h[3]=4>h[4]=1 → right[3]=right[4]+1=2
- i=2: 比较h[2]=2>h[4]=1 → right[2]=2
- i=1: 比较h[1]=3>h[2]=2 → right[1]=right[2]+1=3
- i=0: 比较h[0]=1<h[1]=3 → 不满足递减条件，right[0]=1
right = [1, 3, 2, 2, 1]
计算每个位置的队形长度：
- i=0: 1+1-1=1
- i=1: 2+3-1=4
- i=2: 2+2-1=3
- i=3: 3+2-1=4
- i=4: 1+1-1=1
最大队形长度为4，对应的队形可以是[1,3,2,1]或[1,3,4,1]
- 算法复杂度：
- 时间复杂度：O(n²)，需要两层循环
- 空间复杂度：O(n)，需要两个辅助数组
- 关键点：
- 这个问题本质上是求每个位置作为"山峰"时的最长递增递减序列
- 需要减去1是因为中间位置被重复计算了一次
- 注意严格递增递减的条件（使用<和>而不是≤和≥）