K次串联后最大子数组和的变种——带循环限制
字数 4159 2025-12-07 11:30:39

K次串联后最大子数组和的变种——带循环限制

一、题目描述

我们有一个长度为 n 的整数数组 arr，可以将其重复连接 k 次，得到一个长度为 n * k 的新数组。
但在这个变种问题中，增加一个循环限制：

我们允许从新数组的任意位置开始，选取一个长度不超过 m 的连续子数组（m 是给定的正整数），并且这个子数组可以跨越原始数组的边界（即从末尾回到开头），但前提是总长度 ≤ m，并且只能在同一个“循环数组”表示中取连续段。

目标：在满足上述限制下，找到这个循环数组中长度不超过 m 的连续子数组的最大和。

示例：

arr = [1, -2, 3]
k = 2
m = 4

重复连接得到：[1, -2, 3, 1, -2, 3]
但限制是长度不超过 m=4 且可循环跨越，但这里循环跨越指的是：如果我们只连接一次（k=1），它本身就是循环的，可以在末尾接开头取一段，但长度 ≤ m。
不过题中“K次串联”意味着新数组长度为 n*k，我们可在这上面取长度 ≤ m 的连续子数组，可以跨越边界到开头（循环）。
实际上，为了不超出数组范围，我们可以将原数组复制两次（长度 2n）来模拟循环，但只允许取长度 ≤ m 的窗口。

更精确的描述：
给定数组 arr 长度 n，整数 k ≥ 1，整数 m ≥ 1。
构造新数组 B = arr + arr + ... + arr（k 次），长度 n*k。
我们需要在循环意义下（即 B 被视为循环数组）找长度 ≤ m 的连续子段的最大和。

注意：由于是循环数组，子段可以从 B 中间开始，到末尾后再回到 B 的开头继续取，但总长度不超过 m。
实际上，因为 B 是 arr 的重复，在 B 上跨越一次边界就等于在 arr 上跨越一次边界，但重复 k 次保证了跨越一次不会超出数组，只要 m ≤ n*k。

但为了简化，我们假设 m ≤ n*k，否则就是整个数组的和。

二、问题分析与转换

1. 循环数组的最大子数组和（无长度限制）

经典问题：在一个循环数组中（即末尾与开头相连），无长度限制的最大子数组和 = max(原数组的最大子数组和, 总和 − 原数组的最小子数组和)。
这是因为最大子数组可能是：

  • 不跨越边界的，就是普通最大子段和；
  • 跨越边界的，等于总和减去中间的最小子段和（中间那部分不取）。

2. 加入长度 ≤ m 的限制

在循环数组中，如果我们要找长度 ≤ m 的最大和子数组，有两种情况：

情况 1：不跨越边界（在数组的某一段连续位置，长度 ≤ m） → 变成“长度不超过 m 的最大子数组和”，可用滑动窗口或前缀和+单调队列。

情况 2：跨越边界（从末尾到开头的一段连续，总长度 ≤ m） → 等价于取数组的末尾一段和开头一段拼接。
设数组总长为 L = n*k，跨越边界时，子数组 = 后缀 + 前缀，且后缀长度 a，前缀长度 b，a+b ≤ m，且 a,b ≥ 0。
目标：max(后缀和 + 前缀和)。

但这里要注意，因为我们可以在 B 上任意位置开始，所以跨越边界只是循环数组的一种表示。我们可以将 B 视为循环数组，但 B 是 k 个 arr 的重复，所以跨越边界时可能会跨越重复块。

关键简化：
由于 arr 重复 k 次，B 的任意长度 m 的连续子数组，在循环意义下，等价于在 arr 重复两次（长度 2n）的数组上取长度 ≤ m 的窗口（因为 m ≤ n*k，但如果 k 很大，我们只需复制两次 arr 并连接起来，然后在这个长度为 2n 的数组上做滑动窗口最大和，但窗口长度 ≤ m）。
为什么？
任何长度 ≤ m 的循环窗口，不会超过 2n 长度，因为如果 m ≤ n，那直接在一个 n 的循环数组上取，等价于在 2n 的普通数组上任意起点取长度 ≤ m 的窗口（包括跨越边界的情况）；
如果 m > n，那最大长度 m 可能包含超过一个完整 arr，但我们仍可在 2n 的扩展数组上做，因为循环窗口最多跨越一次边界，而 2n 足够覆盖一次跨越。

结论转换：
设 newArr = arr + arr（长度 2n）。
问题变成：在 newArr 上，找长度 ≤ m 的连续子数组的最大和，但注意 m 可能 > n，但 m ≤ 2n 吗？
如果 m > 2n，那我们可以取整个 2n 的和，但 m 最大是 n*k，如果 k=2 则 m ≤ 2n，如果 k>2 则 m 可能大于 2n，但此时在循环数组中，我们可以取多个完整块。

事实上，如果 m ≥ n，那么最大和可能是多个完整块的组合。
但完整块的总和如果为负数，就不会取超过一个完整块。

因此，我们可以分开讨论 m ≥ n 和 m < n 的情况。

三、动态规划解法思路

我们定义：

  • sumAll = arr 所有元素的和
  • maxSub = arr 的最大子数组和（无长度限制）
  • minSub = arr 的最小子数组和（无长度限制）
  • maxSumLenLimit = 在 arr 中长度不超过 m 的最大子数组和（用单调队列或动态规划）

情况 m < n：
此时无法取到整个 arr，循环数组的最长子段 ≤ m 可能跨越边界，但跨越时长度 ≤ m 仍小于 n，所以等价于在 2n 的扩展数组上做滑动窗口最大和，用单调队列维护前缀和。

情况 m ≥ n：
可以取整个 arr 一次或多次。
设块数 t = m // n，余数 r = m % n。

最大和可能是：

  1. 取 t 个完整块，再加上在剩余长度 r 内在 arr 中取最大前缀和（在开头）和最大后缀和（在末尾）的组合，但要注意是循环的，所以可以取 t 个完整块，再在下一块中取长度 r 的窗口。
    但实际上，我们只需考虑最多 2 个完整块，因为如果 sumAll ≤ 0，取更多完整块不会增加和。

所以算法：

  • 如果 sumAll > 0，最大和 = t * sumAll + 在 arr 中长度不超过 r 的最大窗口和（但要注意跨越边界时，可以取 arr 的后缀+前缀，长度和为 r）
  • 如果 sumAll ≤ 0，则只取长度不超过 m 的窗口，此时 m ≥ n 时，最大窗口可能就是某个长度不超过 n 的最大窗口，因为再多取完整块会减少和。

但这样太复杂，我们换一种更通用且精确的 DP 方法。

四、通用解法：单调队列求长度不超过 m 的最大子数组和（循环数组）

步骤：

  1. 将原数组 arr 重复两次，得到长度为 2n 的数组 A。

  2. 如果 m ≥ 2n，那么在循环数组中长度不超过 m 的最大和，等价于在 A 上取整个 A 的和（如果 sumAll > 0 则可能取更多完整块）。
    但这里 m 可能大于 2n，如果 sumAll > 0，则最大和 = (m // n) * sumAll + 在 arr 中长度不超过 m%n 的最大窗口和（循环窗口），注意 m%n 可能跨越边界。
    如果 sumAll ≤ 0，最大和 = 在 arr 中长度不超过 min(m, 2n) 的窗口最大和。

  3. 所以最终算法：

    • 计算 sumAll。
    • 用单调队列在长度为 2n 的数组 A 上计算长度不超过 min(m, 2n) 的最大窗口和，记为 res1。
    • 如果 sumAll > 0 且 m > 2n：
      t = m // n, r = m % n
      在 arr 上计算长度不超过 r 的最大循环窗口和（即长度 ≤ r 的跨越边界的窗口最大和），这可以用前缀和+单调队列在 2n 的 A 上计算长度不超过 r 的最大窗口和，但要注意窗口长度 ≤ r 且可以跨越 arr 的边界，即从 A 的任意位置开始取长度 ≤ r 的子数组，取最大值。
      然后答案 = max(res1, t * sumAll + 跨越边界长度 r 的最大窗口和)
    • 否则答案 = res1。

五、单调队列求长度不超过 L 的最大窗口和

对于数组 B 长度为 len，求长度不超过 L 的最大窗口和：

  1. 计算前缀和数组 pre，pre[0] = 0, pre[i] = B[0]+...+B[i-1]。
  2. 对每个 i，我们找 j 满足 i - L ≤ j < i，使得 pre[i] - pre[j] 最大，即找 pre[j] 最小。
  3. 用单调队列维护滑动窗口最小值。

六、示例演示

例：arr = [1, -2, 3], n=3, k=2, m=4。

sumAll = 2 > 0。
m=4, n=3, 因为 m < 2n=6，所以只用计算在 2n 数组 A = [1,-2,3,1,-2,3] 上长度 ≤ 4 的最大窗口和。

前缀和 pre = [0,1,-1,2,3,1,4]
L=4，用单调队列：
i=1, 窗口 j∈[0,0], pre[j]=0, sum=1
i=2, 窗口 j∈[0,1], min pre=0, sum=-1
i=3, 窗口 j∈[0,2], min pre=-1, sum=3
i=4, 窗口 j∈[0,3], min pre=-1, sum=4
i=5, 窗口 j∈[1,4], min pre=-1, sum=3
i=6, 窗口 j∈[2,5], min pre=1, sum=3

最大值为 4（子数组 [3,1] 和 1-(-1)=4，对应 A[2..4]? 检查：A[2]=3, A[3]=1，和=4，长度=2，符合）。

所以答案是 4。

七、时间复杂度与空间复杂度

  • 构造 2n 的数组 O(n)
  • 单调队列求长度不超过 L 的最大窗口和 O(n)
  • 总 O(n)

如果 m 很大，需要额外计算跨越多个完整块的情况，但也是 O(n)。

八、核心状态转移方程（思路总结）

这个问题没有显式的经典 DP 递推式，但核心是滑动窗口最大值的变形。
状态定义：
设 dp[i] 为以 i 结尾的长度不超过 m 的最大子数组和，但循环数组需要复制一次。
但更常用的方法是前缀和+单调队列。

这样我们就完整解决了“K次串联后最大子数组和带循环限制”问题。

K次串联后最大子数组和的变种——带循环限制 一、题目描述 我们有一个长度为 n 的整数数组 arr ，可以将其 重复连接 k 次 ，得到一个长度为 n * k 的新数组。 但在这个变种问题中，增加一个 循环限制 ： 我们允许从新数组的任意位置开始，选取一个 长度不超过 m 的连续子数组（ m 是给定的正整数），并且这个子数组 可以跨越原始数组的边界 （即从末尾回到开头），但前提是 总长度 ≤ m ，并且只能在同一个“循环数组”表示中取连续段。 目标 ：在满足上述限制下，找到这个循环数组中长度不超过 m 的连续子数组的最大和。 示例 ： 重复连接得到： [1, -2, 3, 1, -2, 3] 但限制是 长度不超过 m=4 且可循环跨越，但这里循环跨越指的是：如果我们只连接一次（k=1），它本身就是循环的，可以在末尾接开头取一段，但长度 ≤ m。 不过题中“K次串联”意味着新数组长度为 n* k，我们可在这上面取长度 ≤ m 的连续子数组， 可以跨越边界到开头（循环） 。 实际上，为了不超出数组范围，我们可以 将原数组复制两次 （长度 2n）来模拟循环，但只允许取长度 ≤ m 的窗口。 更精确的描述 ： 给定数组 arr 长度 n，整数 k ≥ 1，整数 m ≥ 1。 构造新数组 B = arr + arr + ... + arr （k 次），长度 n* k。 我们需要在循环意义下（即 B 被视为循环数组）找长度 ≤ m 的连续子段的最大和。 注意 ：由于是循环数组，子段可以从 B 中间开始，到末尾后再回到 B 的开头继续取，但总长度不超过 m。 实际上，因为 B 是 arr 的重复，在 B 上跨越一次边界就等于在 arr 上跨越一次边界，但重复 k 次保证了跨越一次不会超出数组，只要 m ≤ n* k。 但为了简化，我们假设 m ≤ n* k，否则就是整个数组的和。 二、问题分析与转换 1. 循环数组的最大子数组和（无长度限制） 经典问题：在一个循环数组中（即末尾与开头相连），无长度限制的最大子数组和 = max(原数组的最大子数组和, 总和 − 原数组的最小子数组和)。 这是因为最大子数组可能是： 不跨越边界的，就是普通最大子段和； 跨越边界的，等于总和减去中间的最小子段和（中间那部分不取）。 2. 加入长度 ≤ m 的限制 在循环数组中，如果我们要找长度 ≤ m 的最大和子数组，有两种情况： 情况 1 ：不跨越边界（在数组的某一段连续位置，长度 ≤ m） → 变成“长度不超过 m 的最大子数组和”，可用滑动窗口或前缀和+单调队列。 情况 2 ：跨越边界（从末尾到开头的一段连续，总长度 ≤ m） → 等价于取数组的末尾一段和开头一段拼接。 设数组总长为 L = n* k，跨越边界时，子数组 = 后缀 + 前缀，且后缀长度 a，前缀长度 b，a+b ≤ m，且 a,b ≥ 0。 目标：max(后缀和 + 前缀和)。 但这里要注意，因为我们可以在 B 上任意位置开始，所以跨越边界只是 循环数组 的一种表示。我们可以将 B 视为循环数组，但 B 是 k 个 arr 的重复，所以跨越边界时可能会跨越重复块。 关键简化 ： 由于 arr 重复 k 次，B 的任意长度 m 的连续子数组，在循环意义下，等价于在 arr 重复两次（长度 2n）的数组上取长度 ≤ m 的窗口（因为 m ≤ n* k，但如果 k 很大，我们只需复制两次 arr 并连接起来，然后在这个长度为 2n 的数组上做滑动窗口最大和，但窗口长度 ≤ m）。 为什么？ 任何长度 ≤ m 的循环窗口，不会超过 2n 长度，因为如果 m ≤ n，那直接在一个 n 的循环数组上取，等价于在 2n 的普通数组上任意起点取长度 ≤ m 的窗口（包括跨越边界的情况）； 如果 m > n，那最大长度 m 可能包含超过一个完整 arr，但我们仍可在 2n 的扩展数组上做，因为循环窗口最多跨越一次边界，而 2n 足够覆盖一次跨越。 结论转换 ： 设 newArr = arr + arr（长度 2n）。 问题变成：在 newArr 上，找长度 ≤ m 的连续子数组的最大和，但注意 m 可能 > n，但 m ≤ 2n 吗？ 如果 m > 2n，那我们可以取整个 2n 的和，但 m 最大是 n* k，如果 k=2 则 m ≤ 2n，如果 k>2 则 m 可能大于 2n，但此时在循环数组中，我们可以取多个完整块。 事实上，如果 m ≥ n，那么最大和可能是多个完整块的组合。 但完整块的总和如果为负数，就不会取超过一个完整块。 因此，我们可以分开讨论 m ≥ n 和 m < n 的情况。 三、动态规划解法思路 我们定义： sumAll = arr 所有元素的和 maxSub = arr 的最大子数组和（无长度限制） minSub = arr 的最小子数组和（无长度限制） maxSumLenLimit = 在 arr 中长度不超过 m 的最大子数组和（用单调队列或动态规划） 情况 m < n ： 此时无法取到整个 arr，循环数组的最长子段 ≤ m 可能跨越边界，但跨越时长度 ≤ m 仍小于 n，所以等价于在 2n 的扩展数组上做滑动窗口最大和，用单调队列维护前缀和。 情况 m ≥ n ： 可以取整个 arr 一次或多次。 设块数 t = m // n，余数 r = m % n。 最大和可能是： 取 t 个完整块，再加上在剩余长度 r 内在 arr 中取最大前缀和（在开头）和最大后缀和（在末尾）的组合，但要注意是循环的，所以可以取 t 个完整块，再在下一块中取长度 r 的窗口。 但实际上，我们只需考虑最多 2 个完整块，因为如果 sumAll ≤ 0，取更多完整块不会增加和。 所以算法： 如果 sumAll > 0，最大和 = t * sumAll + 在 arr 中长度不超过 r 的最大窗口和（但要注意跨越边界时，可以取 arr 的后缀+前缀，长度和为 r） 如果 sumAll ≤ 0，则只取长度不超过 m 的窗口，此时 m ≥ n 时，最大窗口可能就是某个长度不超过 n 的最大窗口，因为再多取完整块会减少和。 但这样太复杂，我们换一种更通用且精确的 DP 方法。 四、通用解法：单调队列求长度不超过 m 的最大子数组和（循环数组） 步骤： 将原数组 arr 重复两次，得到长度为 2n 的数组 A。 如果 m ≥ 2n，那么在循环数组中长度不超过 m 的最大和，等价于在 A 上取整个 A 的和（如果 sumAll > 0 则可能取更多完整块）。 但这里 m 可能大于 2n，如果 sumAll > 0，则最大和 = (m // n) * sumAll + 在 arr 中长度不超过 m%n 的最大窗口和（循环窗口），注意 m%n 可能跨越边界。 如果 sumAll ≤ 0，最大和 = 在 arr 中长度不超过 min(m, 2n) 的窗口最大和。 所以最终算法： 计算 sumAll。 用单调队列在长度为 2n 的数组 A 上计算长度不超过 min(m, 2n) 的最大窗口和，记为 res1。 如果 sumAll > 0 且 m > 2n： t = m // n, r = m % n 在 arr 上计算长度不超过 r 的最大循环窗口和（即长度 ≤ r 的跨越边界的窗口最大和），这可以用前缀和+单调队列在 2n 的 A 上计算长度不超过 r 的最大窗口和，但要注意窗口长度 ≤ r 且可以跨越 arr 的边界，即从 A 的任意位置开始取长度 ≤ r 的子数组，取最大值。 然后答案 = max(res1, t * sumAll + 跨越边界长度 r 的最大窗口和) 否则答案 = res1。 五、单调队列求长度不超过 L 的最大窗口和 对于数组 B 长度为 len，求长度不超过 L 的最大窗口和： 计算前缀和数组 pre，pre[ 0] = 0, pre[ i] = B[ 0]+...+B[ i-1 ]。 对每个 i，我们找 j 满足 i - L ≤ j < i，使得 pre[ i] - pre[ j] 最大，即找 pre[ j ] 最小。 用单调队列维护滑动窗口最小值。 六、示例演示 例：arr = [ 1, -2, 3 ], n=3, k=2, m=4。 sumAll = 2 > 0。 m=4, n=3, 因为 m < 2n=6，所以只用计算在 2n 数组 A = [ 1,-2,3,1,-2,3 ] 上长度 ≤ 4 的最大窗口和。 前缀和 pre = [ 0,1,-1,2,3,1,4 ] L=4，用单调队列： i=1, 窗口 j∈[ 0,0], pre[ j ]=0, sum=1 i=2, 窗口 j∈[ 0,1 ], min pre=0, sum=-1 i=3, 窗口 j∈[ 0,2 ], min pre=-1, sum=3 i=4, 窗口 j∈[ 0,3 ], min pre=-1, sum=4 i=5, 窗口 j∈[ 1,4 ], min pre=-1, sum=3 i=6, 窗口 j∈[ 2,5 ], min pre=1, sum=3 最大值为 4（子数组 [ 3,1] 和 1-(-1)=4，对应 A[ 2..4]? 检查：A[ 2]=3, A[ 3 ]=1，和=4，长度=2，符合）。 所以答案是 4。 七、时间复杂度与空间复杂度 构造 2n 的数组 O(n) 单调队列求长度不超过 L 的最大窗口和 O(n) 总 O(n) 如果 m 很大，需要额外计算跨越多个完整块的情况，但也是 O(n)。 八、核心状态转移方程（思路总结） 这个问题没有显式的经典 DP 递推式，但核心是 滑动窗口最大值 的变形。 状态定义： 设 dp[ i ] 为以 i 结尾的长度不超过 m 的最大子数组和，但循环数组需要复制一次。 但更常用的方法是前缀和+单调队列。 这样我们就完整解决了“K次串联后最大子数组和带循环限制”问题。