难度：★★★☆☆
类型：数组
方法：动态规划

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。

在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）

此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], ..., C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）

示例 1：

输入：[1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

示例 2：

输入：[5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3：

输入：[3,-1,2,-1]
输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4

示例 4：

输入：[3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

示例 5：

输入：[-2,-3,-1]
输出：-1
解释：从子数组 [-1] 得到最大和 -1

提示：

-30000 <= A[i] <= 30000
1 <= A.length <= 30000
通过次数7,230提交次数21,014

解答

我们先来回顾一下非环形的情况，或者说53题最大子序和的问题。使用动态规划可以方便的解决。

【数组定义】定义数组dp，长度与输入数组nums一致，dp[i]表示以nums[i]结尾的子数组中和最大的连续子数组。

【初始情况】当i=0时，子数组nums[:i+1]中只有一个元素，直接将nums[0]赋值给dp[0]即可。

【递推公式】
对于i位置处的情况，有两种可能性，一种是从dp[i-1]继承过来，也就是nums[i]被添加到以nums[i-1]结尾的子数组中，将原先的子数组做了延长；另一种情况就是原先的子数组到此位置，nums[i]成为新的子数组的开头。我们选取这两种情况的子数组的最大值，填充在当前位置i即可。

dp[i]=max(dp[i-1]+nums[i],nums[i])

【最终返回值】

最终返回dp数组中的最大值即可。

class Solution:
    def maxSubArray(self, nums):
        size = len(nums)
        if size == 0:
            return None
        if size == 1:
            return nums[0]

        dp = [False for _ in range(size)]  # 记录状态：当前以i结尾的最大值记录在里面
        dp[0] = nums[0]

        for i in range(1, size):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])  # 记录最大状态
        return max(dp)

现在的情况是，原始数组首尾连接，形成环形，这样一来，我们就需要考虑另外一种情况，也就是尾部一段连接开头一段的情况。我们从相反的角度来思考这种情况。假设数组被分成了ABC三段，能够使得子数组的和最大的是C+A段，注意A段和C段在表达形势上是断开的，但是在物理意义上是连续的，那么对于剩下的中间的B段，在形势上就是连续的，而且这种状况下，B段的和是最小的。如果我们能够找到最小和的连续子数组，就从另一个角度确定了最大和的连续子数组（剩下的那两部分就是），问题就转化为，如何找到非环形列表的最小和的连续子数组。很显然，我们可以用与上述类似的动态规划的方法来解决。

这里就不再使用数组了，因为我们只关心当前最新的最佳结果，因此可以降低一下空间复杂度，cur_min和res_min分别代表当前子数组最小值，以及研究到现在为止的最佳结果。遍历数组，对于当前元素num，递推公式为cur_min = min(num+cur_min, num)，并且用res_min及时记录最新结果。当我们找到了最小和的连续子数组，那么剩下的两部分就组成了最大和的连续子数组，其和就是sum(A) - res_min。

综上，根据最大和的连续子数组在形式上是连续的或者断开的，这两种情况选其最优即可。需要补充的是，这里需要判断数组元素全部为负数的情况，这时直接返回最大值。

class Solution:
    def maxSubarraySumCircular(self, A):
        res = cur = 0
        for num in A:
            cur = max(cur+num, num)
            res = max(res, cur)

        if res == 0:
            res = max(A)
            return res

        cur_min = res_min = 0
        for num in A:
            cur_min = min(num+cur_min, num)
            res_min = min(res_min, cur_min)

        res = max(res, sum(A) - res_min)
        return res

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析