区间动态规划例题：最大子数组和的循环移位版本 题目描述 给定一个长度为 n 的环形整数数组 nums，你可以执行任意次循环移位操作（每次移位将数组元素向左或向右移动一位）。请找出通过循环移位后，该数组的最大子数组和（子数组要求连续）。注意：子数组可以为空，此时和为 0。 例如，对于数组 [ 1, -2, 3, -2]，循环移位后可能得到 [ 3, -2, 1, -2]，其最大子数组和为 3（子数组 [ 3]）。但最优解是通过移位得到 [ 3, -2, 1, -2] 的另一种排列？实际上，原始数组的最大子数组和是 3（[ 3 ]），但通过循环移位，我们可以得到更大的子数组和吗？这个问题要求我们利用循环移位最大化连续子数组的和。 解题过程 步骤 1：问题分析 环形数组的循环移位等价于将数组视为环形，然后选取一个起点展开成线性数组。 目标是在所有可能的循环移位中，找到最大的连续子数组和。 关键观察：最大子数组和可能出现在两种情况下： 非环形情况 ：最大子数组不跨越数组的首尾（即问题退化为普通的最大子数组和问题）。 环形情况 ：最大子数组跨越数组的首尾（即子数组由数组末尾的一部分和开头的一部分组成）。 步骤 2：转化为已知问题 设数组总和为 total。 非环形情况的最大子数组和可以用 Kadane 算法直接求出，记为 max_ non_ circular。 环形情况的最大子数组和等价于 total - 最小子数组和（因为跨越首尾的子数组和 = total - 中间剩余部分的和，而中间剩余部分是一个连续子数组，其和应最小）。 因此，环形情况的最大子数组和为 max_ circular = total - min_ subarray_ sum，其中 min_ subarray_ sum 是数组的最小子数组和（注意：如果最小子数组和为负数，且 total 固定，则 max_ circular 可能大于 total）。 特殊情况：如果数组全为负数，则最大子数组和为 0（空子数组）。 步骤 3：动态规划状态定义 定义 dp_ max[ i ] 表示以第 i 个元素结尾的最大子数组和。 定义 dp_ min[ i ] 表示以第 i 个元素结尾的最小子数组和。 初始状态：dp_ max[ 0] = nums[ 0], dp_ min[ 0] = nums[ 0 ]。 递推关系： dp_ max[ i] = max(nums[ i], dp_ max[ i-1] + nums[ i ]) dp_ min[ i] = min(nums[ i], dp_ min[ i-1] + nums[ i ]) 步骤 4：计算最终结果 遍历数组，计算全局最大子数组和 max_ non_ circular = max(dp_ max[ i]) 和全局最小子数组和 min_ subarray_ sum = min(dp_ min[ i ])。 如果 max_ non_ circular < 0，说明数组全为负数，结果为 0。 否则，结果为 max(max_ non_ circular, total - min_ subarray_ sum)。 注意：如果最小子数组和等于 total（即数组全为正数），则环形情况的结果为 total，但此时 max_ non_ circular 也为 total，所以结果一致。 步骤 5：示例验证 以 nums = [ 1, -2, 3, -2 ] 为例： total = 1 + (-2) + 3 + (-2) = 0 dp_ max 计算： i=0: dp_ max[ 0 ]=1 i=1: dp_ max[ 1 ]=max(-2, 1-2)=-1 → 但实际应取 max(当前值, 前面和+当前值)，正确计算： i=0: max=1 i=1: max(-2, 1-2)=max(-2,-1)=-1，但全局max需记录，此处全局max_ non_ circular=1 i=2: max(3, -1+3)=max(3,2)=3 → 全局max_ non_ circular=3 i=3: max(-2, 3-2)=max(-2,1)=1 → 全局max_ non_ circular=3 dp_ min 计算： i=0: min=1 i=1: min(-2, 1-2)=min(-2,-1)=-2 → 全局min_ subarray_ sum=-2 i=2: min(3, -2+3)=min(3,1)=1 i=3: min(-2, 1-2)=min(-2,-1)=-2 → 全局min_ subarray_ sum=-2 total - min_ subarray_ sum = 0 - (-2) = 2 最终结果 = max(3, 2) = 3。 说明此例中循环移位不能得到比 3 更大的子数组和。 步骤 6：边界情况处理 数组全为负数：max_ non_ circular < 0，返回 0。 数组全为正数：max_ non_ circular = total - min_ subarray_ sum = total，结果正确。 数组总和为 0：环形情况可能得到正数（如示例中 total=0 但 min_ subarray_ sum 为负）。 通过以上步骤，我们利用动态规划（Kadane 算法变种）解决了循环移位下的最大子数组和问题。