区间动态规划例题：环形游乐场中的最优游览路线问题

题目描述

你是一个游乐场导游，游乐场是一个环形路线，上面有 n 个景点，编号为 0 到 n-1（环形排列，即景点 n-1 的下一个是景点 0）。每个景点 i 有一个“游览收益” value[i]（可以为正、负或零）。你需要选择一段连续的景点区间进行游览（区间长度至少为 1，且由于是环形，区间可以从末尾绕回开头），使得这段区间内所有景点的收益之和最大。但由于体力和时间的限制，你最多只能游览 恰好 k 个景点（即选择的连续区间长度恰好等于 k），且不能重复游览同一个景点。

输入：

• 一个整数数组 values，长度为 n，表示环形排列的景点收益。
• 一个整数 k（1 ≤ k ≤ n）。

输出：

• 一个整数，表示在恰好游览 k 个连续景点的条件下，所能获得的最大收益总和。

示例：

n = 5, values = [1, -2, 3, -1, 5], k = 3
环形排列：景点 0(1), 1(-2), 2(3), 3(-1), 4(5)
可能的长度为 3 的连续区间：
- [0,1,2]：收益 = 1 + (-2) + 3 = 2
- [1,2,3]：收益 = (-2) + 3 + (-1) = 0
- [2,3,4]：收益 = 3 + (-1) + 5 = 7
- [3,4,0]：收益 = (-1) + 5 + 1 = 5
- [4,0,1]：收益 = 5 + 1 + (-2) = 4
最大收益为 7。

解题思路

这是一个结合了 “环形数组” 与 “定长区间” 的区间动态规划问题。核心挑战在于环形结构下，如何高效计算所有长度为 k 的连续区间的收益和，并取最大值。

我们分步进行：

第 1 步：问题转化（环形转线性）

对于环形问题，常见的处理方式是将原数组复制一份接在后面，形成一个长度为 2n 的线性数组。这样，原环形中任意一个长度为 k 的连续区间，都会在这个扩展数组中对应一个长度为 k 的连续子数组。因此，问题转化为：在长度为 2n 的扩展数组中，寻找所有长度为 k 的子数组的最大和，但需确保子数组不超过原环形范围（即起始位置在 [0, n-1] 内）。

第 2 步：定义状态

我们可以定义动态规划状态：

• dp[i] 表示以第 i 个景点（在扩展数组中）结尾、长度为 k 的子数组的收益和。

然而，因为 k 是固定的，我们可以用更高效的方法：前缀和。

第 3 步：前缀和计算

设扩展数组为 extended = values + values（即两个原数组拼接），长度 2n。
计算前缀和数组 prefixSum：

prefixSum[0] = 0
prefixSum[i+1] = prefixSum[i] + extended[i]  (i 从 0 到 2n-1)

那么，任意子数组 [l, r]（左闭右闭）的和为：

sum(l, r) = prefixSum[r+1] - prefixSum[l]

我们希望子数组长度恰好为 k，即 r - l + 1 = k，所以：

sum = prefixSum[i+1] - prefixSum[i+1-k]   (其中 i 为区间右端点索引)

第 4 步：滑动窗口求最大值

由于 k 固定，我们可以用滑动窗口的方式，遍历所有可能的右端点 i（在扩展数组中），并计算以 i 结尾的长度为 k 的子数组和，同时保证子数组起始索引在 [0, n-1] 内（对应原环形区间）。

具体步骤：

1. 构建扩展数组 extended。
2. 计算前缀和 prefixSum。
3. 遍历右端点 i 从 k-1 到 2n-1（因为子数组长度至少为 k）：
   • 计算当前子数组和：currentSum = prefixSum[i+1] - prefixSum[i+1-k]
   • 检查子数组起始索引 start = i+1-k 是否满足 start < n（即起始点仍在原数组范围内）：
     • 若满足，更新最大收益 maxSum = max(maxSum, currentSum)
4. 返回 maxSum。

此方法时间复杂度为 O(n)，空间复杂度为 O(n)（用于前缀和）。

第 5 步：示例演算

以 values = [1, -2, 3, -1, 5], k = 3 为例：

1. 扩展数组 extended = [1, -2, 3, -1, 5, 1, -2, 3, -1, 5]（长度 10）。
2. 计算前缀和 prefixSum = [0, 1, -1, 2, 1, 6, 7, 5, 8, 7, 12]（长度 11）。
3. 遍历 i 从 2 到 9：
   • i=2：sum = prefixSum[3]-prefixSum[0] = 2-0=2，起始索引 start=0，有效 → maxSum=2
   • i=3：sum = prefixSum[4]-prefixSum[1] = 1-1=0，start=1，有效 → maxSum=2
   • i=4：sum = prefixSum[5]-prefixSum[2] = 6-(-1)=7，start=2，有效 → maxSum=7
   • i=5：sum = prefixSum[6]-prefixSum[3] = 7-2=5，start=3，有效 → maxSum=7
   • i=6：sum = prefixSum[7]-prefixSum[4] = 5-1=4，start=4，有效 → maxSum=7
   • i=7：sum = prefixSum[8]-prefixSum[5] = 8-6=2，start=5（≥n=5），无效（超出原数组起始范围）
   • i=8：start=6，无效
   • i=9：start=7，无效
4. 最终结果 maxSum = 7，与示例一致。

第 6 步：边界情况考虑

• k = n：此时整个环形必须全部游览，结果就是整个数组的和（如果和为负数，则说明最大收益可能来自某个长度为 n 的区间，但因为必须恰好 k 个景点，所以只能全选）。
• k = 1：相当于找数组中的最大值。
• 所有收益为负数：最大收益为最大的单个负数（因为必须选 k 个，所以是长度为 k 的区间中最大的和）。
• n = 1：此时 k 也必须为 1，结果就是该景点的收益。

第 7 步：总结

本题通过 “环形转线性” 与 “前缀和 + 滑动窗口” 的方法，将原本复杂的环形区间定长求和问题，转化为线性数组上的固定窗口最大值问题。关键在于：

1. 将数组复制一次，得到扩展线性数组。
2. 用前缀和快速计算任意定长子数组的和。
3. 遍历所有有效右端点，检查起始索引是否在原数组范围内。

这个方法高效且易于实现，适用于类似“环形定长区间最大和”的问题场景。