区间动态规划例题：最大子数组和问题（环形数组版本） 题目描述 给定一个环形整数数组 nums （即数组首尾相连），请找出其中连续子数组的最大和。注意：子数组最多只能包含固定数组 nums 的每个元素一次（在环形情况下，首尾元素可相连形成子数组）。要求返回最大可能的和。 示例 输入： nums = [5, -3, 5] 输出： 10 解释：从最后一个元素开始，绕到第一个元素，子数组 [5, 5] 的和为 10。 解题思路 环形数组的最大子数组和有两种情况： 最大子数组不跨越首尾 ：此时问题退化为普通的最大子数组和问题（Kadane 算法）。 最大子数组跨越首尾 ：此时最大子数组包含首部的一部分和尾部的一部分。可转换为求整个数组和减去最小子数组和（若最小子数组和为负，则最大子数组和就是整个数组和）。 动态规划步骤 定义状态 max_dp[i] ：以 nums[i] 结尾的最大子数组和（不跨越首尾）。 min_dp[i] ：以 nums[i] 结尾的最小子数组和（用于计算跨越首尾的情况）。 状态转移方程 最大子数组和（普通 Kadane） ： max_dp[i] = max(nums[i], max_dp[i-1] + nums[i]) 最小子数组和 ： min_dp[i] = min(nums[i], min_dp[i-1] + nums[i]) 处理环形情况 若整个数组均为负数，直接返回 max(nums) 。 否则，最大子数组和 = max(最大普通子数组和, 总和 - 最小子数组和) 。 边界条件 max_dp[0] = min_dp[0] = nums[0] 遍历从 i=1 到 n-1 。 示例推导 以 nums = [5, -3, 5] 为例： 普通最大子数组和 （Kadane）： max_dp[0]=5 , max_dp[1]=max(-3, 5-3)=2 , max_dp[2]=max(5, 2+5)=7 → 最大为 7。 最小子数组和 ： min_dp[0]=5 , min_dp[1]=min(-3, 5-3)=-3 , min_dp[2]=min(5, -3+5)=2 → 最小为 -3。 环形情况 ：总和 = 7， 总和 - 最小子数组和 = 7 - (-3) = 10 。 最终结果： max(7, 10) = 10 。 复杂度分析 时间复杂度：O(n)，仅需遍历数组一次。 空间复杂度：O(1)，可优化为只维护前一个状态的变量。 关键点 环形问题通过分类讨论转化为两个线性问题。 注意全负数情况的特殊处理。