https://leetcode.cn/problems/maximum-sum-circular-subarray/
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
示例 1：
输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：
输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
提示：
n == nums.length
1 <= n <= 3 * 10^4
-3 * 104 <= nums[i] <= 3 * 10^4
- 动态规划
- 暂无
数据范围是 10 ^ 4 意味着暴力的 n ^ 2 是不能接受的。
如果不考虑环这个条件，那么这是一道经典的子序和问题。对于子序和不熟悉的同学，可以看下我之前的博文：https://lucifer.ren/blog/2020/06/20/LSS/
简单来说，如果是不考虑环的子序和，我们可以定义 dp[i] 为以 nums[i] 结尾的最大子序和，那么答案就是 max(dp)。
那么对于 nums[i] 来说， 其可以和 nums[i-1] 结合形成子序列，也可以自立门户以 nums[i] 开头形成子序列。
-
和 nums[i-1] 结合形成子序列，那么nums[i-1] 前面还有几个元素呢？这其实已经在之前计算 dp[i-1] 的时候计算好了。因此实际上这种情况的最大子序和是 dp[i-1] + nums[i]
-
自立门户以 nums[i] 开头形成子序列，这种浅情况就是 nums[i]
基于贪心的思想，也可以统一成一个式子 max(dp[i-1], 0) + nums[i]
接下来，我们考虑环。如果有环，那么最大子序和，要么就和普通的最大子序和一样只是普通的一段子序列，要么就是首尾两段加起来的和最大。
因此我们只需要额外考虑如何计算首尾两段的情况。对于这种情况其实等价于计算中间一段“最小子序和”，然后用数组的总和减去“最小子序和” 就是答案。而求最小子序和和最大子序和基本没有差异，将 max 改为 min 即可。
- 其中一种情况（两段子序和）：转化为 sum(nums) - 最小子序和
- 语言支持：Python3
Python3 Code:
class Solution:
# 最小子序和
def solve1(self, A):
A = A
dp = [inf] * len(A)
for i in range(len(A)):
dp[i] = min(A[i], dp[i - 1] + A[i])
return min(dp)
# 最大子序和
def solve2(self, A):
A = A
dp = [-inf] * len(A)
for i in range(len(A)):
dp[i] = max(A[i], dp[i - 1] + A[i])
return max(dp)
def maxSubarraySumCircular(self, nums: List[int]) -> int:
ans1 = sum(nums) - self.solve1(nums)
ans2 = self.solve2(nums)
if ans1 == 0: ans1 = max(nums) # 不能为空，那就选一个最大的吧
return max(ans1, ans2)复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
