线性动态规划：最大子序和（进阶版——环形数组） 题目描述 给定一个长度为 n 的环形整数数组 nums（即数组首尾相连），请找出环形数组中的一个连续子数组，使得该子数组的元素和最大，并返回这个最大和。注意：子数组最多只能包含每个元素一次。 解题过程循序渐进讲解 步骤1：理解环形数组的特殊性 在环形数组中，连续子数组可能出现在两种位置： 常规情况 ：子数组位于数组中间（不跨越首尾），此时问题退化为普通数组的"最大子序和"。 环形情况 ：子数组跨越数组首尾（例如包含 nums[ n-1] 和 nums[ 0 ]），此时子数组由数组末尾的一段和数组开头的一段组成。 关键思路 ：环形数组的最大子序和 = max(常规情况最大和, 环形情况最大和) 步骤2：常规情况的最大子序和 对于普通数组，最大子序和可以用 Kadane 算法求解： 定义 dp[ i] 表示以 nums[ i ] 结尾的最大子序和。 状态转移：dp[ i] = max(nums[ i], dp[ i-1] + nums[ i ]) 常规情况最大和 max_ normal = max(dp[ 0..n-1 ]) 步骤3：环形情况的最大子序和 环形情况下的最大和 = 数组总和 - 最小子序和 解释：当子数组跨越首尾时，剩余中间部分必然是一个连续子数组（且不跨越首尾）。要使首尾连接部分的和最大，等价于让中间剩余部分的和最小。 注意：如果最小子序和等于数组总和（即所有数为负数），说明整个数组都是负数，此时环形情况不成立，应取常规情况的最大值（即最大单个负数）。 步骤4：最小子序和的求法 类似 Kadane 算法，求最小子序和 min_ subarray： 定义 dp_ min[ i] 表示以 nums[ i ] 结尾的最小子序和。 状态转移：dp_ min[ i] = min(nums[ i], dp_ min[ i-1] + nums[ i ]) min_ subarray = min(dp_ min[ 0..n-1 ]) 步骤5：整合两种情况 环形数组最大和 = 如果数组全为负数（max_ normal < 0）：直接返回 max_ normal 否则：max(max_ normal, total_ sum - min_ subarray) 步骤6：边界处理 数组长度为 1 时，直接返回 nums[ 0 ] 注意环形情况中，如果最小子序和等于数组总和，说明取了整个数组，此时环形情况无效（因为子数组不能重复包含元素），故取 max_ normal 示例验证 例：nums = [ 5, -3, 5 ] 常规情况最大和：5（[ 5]）或 5（[ 5]）或 7（[ 5, -3, 5]）→ max_ normal=7 数组总和 total_ sum=7，最小子序和 min_ subarray=-3（[ -3 ]） 环形情况最大和=7-(-3)=10（即 [ 5,5 ] 跨越首尾） 最终结果=max(7,10)=10 通过以上步骤，即可系统解决环形数组的最大子序和问题。