区间动态规划例题：合唱队形问题（最长递增递减子序列）

题目描述
有n位学生站成一排，每个学生有一个身高h[i]。现在需要请出一些学生出列，使得剩下的学生排成合唱队形：即存在一个中间位置k，使得左边部分L1, L2, ..., Lk的身高严格递增，右边部分Rk, Rk+1, ..., Rn的身高严格递减。求最少需要出列多少学生。

解题思路分析
这个问题可以转化为：找到最长的先严格递增后严格递减的子序列（峰值可包含在两侧），然后用总人数减去这个最长子序列的长度即为最少出列人数。

详细解题步骤

1. 问题转化

   • 我们需要找到一个位置k作为峰值
   • 峰值左侧是严格递增序列（包含k）
   • 峰值右侧是严格递减序列（包含k）
   • 这相当于求每个位置作为峰值时的最长递增子序列长度 + 最长递减子序列长度 - 1

2. 定义状态

   • left[i]：以第i个学生为结尾的最长严格递增子序列长度
   • right[i]：以第i个学生为开头的最长严格递减子序列长度

3. 状态转移方程

   对于left数组（从左往右计算）：

   left[i] = 1  // 初始化为1（至少包含自己）
   对于每个 j < i：
       如果 h[j] < h[i]：
           left[i] = max(left[i], left[j] + 1)
   

   对于right数组（从右往左计算）：

   right[i] = 1  // 初始化为1
   对于每个 j > i：
       如果 h[j] < h[i]：
           right[i] = max(right[i], right[j] + 1)
   

4. 计算每个位置作为峰值的合唱队形长度

   对于每个位置i：
       队形长度 = left[i] + right[i] - 1
   

5. 求最少出列人数

   最少出列人数 = n - max(队形长度 for i in 1..n)
   

完整示例演示

例：学生身高序列为 [186, 186, 150, 200, 160, 130, 197, 220]

1. 计算left数组：

   • i=1: left[1] = 1
   • i=2: 186≮186 → left[2] = 1
   • i=3: 150比前面都小 → left[3] = 1
   • i=4: 200 > 186,186,150 → left[4] = max(1,1+1,1+1,1+1) = 2
   • i=5: 160 > 150 → left[5] = left[3]+1 = 2
   • i=6: 130比前面都小 → left[6] = 1
   • i=7: 197 > 186,186,150,160 → left[7] = max(1,2,2,1,2)+1 = 3
   • i=8: 220 > 所有前面 → left[8] = max(left[1..7])+1 = 4
     left = [1, 1, 1, 2, 2, 1, 3, 4]

2. 计算right数组：

   • i=8: right[8] = 1
   • i=7: 197 > 130? 是 → right[7] = right[8]+1 = 2
   • i=6: 130比后面都小 → right[6] = 1
   • i=5: 160 > 130 → right[5] = right[6]+1 = 2
   • i=4: 200 > 160,130,197? 200>160,130但<197 → right[4] = max(right[5],right[6])+1 = 3
   • i=3: 150 > 130 → right[3] = right[6]+1 = 2
   • i=2: 186 > 150,160,130? 186>150,130但<160,197 → right[2] = max(right[3],right[6])+1 = 3
   • i=1: 186 > 150,160,130? 同上 → right[1] = max(right[3],right[6])+1 = 3
     right = [3, 3, 2, 3, 2, 1, 2, 1]

3. 计算每个位置的合唱队形长度：

   • 位置1: 1+3-1=3
   • 位置2: 1+3-1=3
   • 位置3: 1+2-1=2
   • 位置4: 2+3-1=4
   • 位置5: 2+2-1=3
   • 位置6: 1+1-1=1
   • 位置7: 3+2-1=4
   • 位置8: 4+1-1=4

4. 最终结果：

   • 最长合唱队形长度 = max(3,3,2,4,3,1,4,4) = 4
   • 最少出列人数 = 8 - 4 = 4

算法复杂度分析

• 时间复杂度：O(n²)，需要两层循环计算left和right数组
• 空间复杂度：O(n)，需要两个辅助数组

关键点总结

1. 将问题分解为求每个学生左边的最长递增序列和右边的最长递减序列
2. 峰值学生被计算了两次，需要减1
3. 注意严格递增递减的条件（不能有相等身高）
4. 最终结果是总人数减去最长合唱队形长度