题目地址(918. 环形子数组的最大和)

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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

Uh oh!