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

字数 2298 2025-12-22 17:39:16

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

题目描述
有一个长度为 \(n\) 的整数数组 \(a\)，表示一群学生的身高。现在需要从中选出若干人组成合唱队形，要求选出的队伍满足以下条件：

队伍中的人按顺序排列，其身高先严格递增，然后严格递减。
递增部分和递减部分都至少包含一个人。
整个队伍的总人数尽可能多。

例如，数组 \(a = [1, 3, 2, 4, 5, 2, 1]\)，最长的合唱队形可以是 \([1, 3, 4, 5, 2, 1]\)（递增部分为 1,3,4,5，递减部分为 5,2,1），总人数为 7。

你的任务是找到最长的合唱队形的长度。

解题过程

1. 问题分析

这个问题可以转化为：

对于每个位置 \(i\)，计算以 \(a[i]\) 为最高点（即递增部分的最后一个，递减部分的第一个）的合唱队形的最大长度。
这需要知道两个信息：
1. 以 \(a[i]\) 结尾的最长严格递增子序列的长度（记作 \(L[i]\)）。
2. 以 \(a[i]\) 开头的最长严格递减子序列的长度（记作 \(R[i]\)）。

那么，以 \(a[i]\) 为最高点的合唱队形长度 = \(L[i] + R[i] - 1\)（因为 \(a[i]\) 被重复计算了一次）。
最终答案 = \(\max_{i=1}^{n} (L[i] + R[i] - 1)\)。

2. 计算 \(L[i]\)（从左向右的最长严格递增子序列长度）

定义 \(L[i]\) 表示以 \(a[i]\) 结尾的最长严格递增子序列的长度。
初始化：\(L[1] = 1\)。
对于 \(i = 2\) 到 \(n\)：

遍历 \(j = 1\) 到 \(i-1\)，如果 \(a[j] < a[i]\)，则 \(L[i] = \max(L[i], L[j] + 1)\)。
如果找不到这样的 \(j\)，则 \(L[i] = 1\)。

示例：\(a = [1, 3, 2, 4, 5, 2, 1]\)

\(L[1]=1\)
\(L[2]\)：比 \(a[1]\) 大，所以 \(L[2]=L[1]+1=2\)
\(L[3]\)：比 \(a[1]\) 大，所以 \(L[3]=L[1]+1=2\)
\(L[4]\)：比 \(a[1],a[2],a[3]\) 大，取最大 L+1 = 3（来自 a[2] 或 a[3]）
计算后得到 \(L = [1, 2, 2, 3, 4, 2, 2]\)

3. 计算 \(R[i]\)（从右向左的最长严格递减子序列长度）

实际上，递减子序列从右向左看就是递增。
定义 \(R[i]\) 表示以 \(a[i]\) 开头的最长严格递减子序列的长度，等价于从右向左以 \(a[i]\) 结尾的最长严格递增子序列的长度。

初始化：\(R[n] = 1\)。
对于 \(i = n-1\) 到 \(1\)：

遍历 \(j = i+1\) 到 \(n\)，如果 \(a[j] < a[i]\)，则 \(R[i] = \max(R[i], R[j] + 1)\)。
如果找不到，则 \(R[i] = 1\)。

示例：

\(R[7]=1\)
\(R[6]\)：比 \(a[7]\) 大，所以 \(R[6]=R[7]+1=2\)
\(R[5]\)：比 \(a[6]\) 和 \(a[7]\) 大，取最大 R+1 = 3（来自 a[6]）
计算后得到 \(R = [2, 2, 2, 2, 3, 2, 1]\)

4. 计算合唱队形最大长度

对于每个 \(i\)，合唱队形长度 = \(L[i] + R[i] - 1\)。

\(i=1\)：1+2-1=2
\(i=2\)：2+2-1=3
\(i=3\)：2+2-1=3
\(i=4\)：3+2-1=4
\(i=5\)：4+3-1=6
\(i=6\)：2+2-1=3
\(i=7\)：2+1-1=2

最大值为 6（对应 \(i=5\)，即身高 5 为最高点，递增部分 1,3,4,5，递减部分 5,2,1，总长度 6）。

5. 验证结果

原始数组 \(a = [1, 3, 2, 4, 5, 2, 1]\)
以 \(a[5]=5\) 为最高点：

递增部分（以 5 结尾的最长递增子序列）：1,3,4,5（长度 4）
递减部分（以 5 开头的最长递减子序列）：5,2,1（长度 3）
总长度 = 4+3-1=6。

6. 时间复杂度优化

上述计算 \(L[i]\) 和 \(R[i]\) 的时间复杂度为 \(O(n^2)\)，在 \(n \leq 1000\) 时可行。
如果需要更优的时间复杂度，可以用贪心+二分的 \(O(n \log n)\) 方法求最长递增子序列，但此处由于是区间 DP 专题，我们以 DP 解法为主。

7. 边界情况

如果整个数组严格递增，则最大合唱队形长度只能是 2（因为递减部分至少一个人，需要后面有比最后一个小的数）。
如果 \(n < 3\)，无法同时满足递增和递减部分至少一人，结果为 0 或 2？根据题意，通常要求递增和递减部分都至少一人，所以 \(n \ge 3\) 才有意义。

最终答案：找到所有位置 \(i\) 的 \(L[i] + R[i] - 1\) 的最大值即可。

区间动态规划例题：合唱队形问题（最长“先严格递增再严格递减”子序列）题目描述有一个长度为 \(n\) 的整数数组 \(a\)，表示一群学生的身高。现在需要从中选出若干人组成合唱队形，要求选出的队伍满足以下条件：队伍中的人按顺序排列，其身高先严格递增，然后严格递减。递增部分和递减部分都至少包含一个人。整个队伍的总人数尽可能多。例如，数组 \(a = [ 1, 3, 2, 4, 5, 2, 1]\)，最长的合唱队形可以是 \([ 1, 3, 4, 5, 2, 1 ]\)（递增部分为 1,3,4,5，递减部分为 5,2,1），总人数为 7。你的任务是找到最长的合唱队形的长度。解题过程 1. 问题分析这个问题可以转化为：对于每个位置 \(i\)，计算以 \(a[ i]\) 为最高点（即递增部分的最后一个，递减部分的第一个）的合唱队形的最大长度。这需要知道两个信息：以 \(a[ i]\) 结尾的最长严格递增子序列的长度（记作 \(L[ i ]\)）。以 \(a[ i]\) 开头的最长严格递减子序列的长度（记作 \(R[ i ]\)）。那么，以 \(a[ i]\) 为最高点的合唱队形长度 = \(L[ i] + R[ i] - 1\)（因为 \(a[ i ]\) 被重复计算了一次）。最终答案 = \(\max_ {i=1}^{n} (L[ i] + R[ i ] - 1)\)。 2. 计算 \(L[ i ]\)（从左向右的最长严格递增子序列长度）定义 \(L[ i]\) 表示以 \(a[ i ]\) 结尾的最长严格递增子序列的长度。初始化：\(L[ 1 ] = 1\)。对于 \(i = 2\) 到 \(n\)：遍历 \(j = 1\) 到 \(i-1\)，如果 \(a[ j] < a[ i]\)，则 \(L[ i] = \max(L[ i], L[ j ] + 1)\)。如果找不到这样的 \(j\)，则 \(L[ i ] = 1\)。示例：\(a = [ 1, 3, 2, 4, 5, 2, 1 ]\) \(L[ 1 ]=1\) \(L[ 2]\)：比 \(a[ 1]\) 大，所以 \(L[ 2]=L[ 1 ]+1=2\) \(L[ 3]\)：比 \(a[ 1]\) 大，所以 \(L[ 3]=L[ 1 ]+1=2\) \(L[ 4]\)：比 \(a[ 1],a[ 2],a[ 3]\) 大，取最大 L+1 = 3（来自 a[ 2] 或 a[ 3 ]）计算后得到 \(L = [ 1, 2, 2, 3, 4, 2, 2 ]\) 3. 计算 \(R[ i ]\)（从右向左的最长严格递减子序列长度）实际上，递减子序列从右向左看就是递增。定义 \(R[ i]\) 表示以 \(a[ i]\) 开头的最长严格递减子序列的长度，等价于从右向左以 \(a[ i]\) 结尾的最长严格递增子序列的长度。初始化：\(R[ n ] = 1\)。对于 \(i = n-1\) 到 \(1\)：遍历 \(j = i+1\) 到 \(n\)，如果 \(a[ j] < a[ i]\)，则 \(R[ i] = \max(R[ i], R[ j ] + 1)\)。如果找不到，则 \(R[ i ] = 1\)。示例： \(R[ 7 ]=1\) \(R[ 6]\)：比 \(a[ 7]\) 大，所以 \(R[ 6]=R[ 7 ]+1=2\) \(R[ 5]\)：比 \(a[ 6]\) 和 \(a[ 7]\) 大，取最大 R+1 = 3（来自 a[ 6 ]）计算后得到 \(R = [ 2, 2, 2, 2, 3, 2, 1 ]\) 4. 计算合唱队形最大长度对于每个 \(i\)，合唱队形长度 = \(L[ i] + R[ i ] - 1\)。 \(i=1\)：1+2-1=2 \(i=2\)：2+2-1=3 \(i=3\)：2+2-1=3 \(i=4\)：3+2-1=4 \(i=5\)：4+3-1=6 \(i=6\)：2+2-1=3 \(i=7\)：2+1-1=2 最大值为 6（对应 \(i=5\)，即身高 5 为最高点，递增部分 1,3,4,5，递减部分 5,2,1，总长度 6）。 5. 验证结果原始数组 \(a = [ 1, 3, 2, 4, 5, 2, 1 ]\) 以 \(a[ 5 ]=5\) 为最高点：递增部分（以 5 结尾的最长递增子序列）：1,3,4,5（长度 4）递减部分（以 5 开头的最长递减子序列）：5,2,1（长度 3）总长度 = 4+3-1=6。 6. 时间复杂度优化上述计算 \(L[ i]\) 和 \(R[ i ]\) 的时间复杂度为 \(O(n^2)\)，在 \(n \leq 1000\) 时可行。如果需要更优的时间复杂度，可以用贪心+二分的 \(O(n \log n)\) 方法求最长递增子序列，但此处由于是区间 DP 专题，我们以 DP 解法为主。 7. 边界情况如果整个数组严格递增，则最大合唱队形长度只能是 2（因为递减部分至少一个人，需要后面有比最后一个小的数）。如果 \(n < 3\)，无法同时满足递增和递减部分至少一人，结果为 0 或 2？根据题意，通常要求递增和递减部分都至少一人，所以 \(n \ge 3\) 才有意义。最终答案：找到所有位置 \(i\) 的 \(L[ i] + R[ i ] - 1\) 的最大值即可。