feat:$918

robot · robot · commit b37076730a48 · 2023-07-20T12:26:18.000+08:00
diff --git a/problems/918.maximum-sum-circular-subarray.md b/problems/918.maximum-sum-circular-subarray.md
@@ -0,0 +1,130 @@
+
+## 题目地址(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] 开头形成子序列。
+
+1. 和 nums[i-1] 结合形成子序列，那么nums[i-1] 前面还有几个元素呢？这其实已经在之前计算 dp[i-1] 的时候计算好了。因此实际上这种情况的最大子序和是 dp[i-1] + nums[i]
+
+2. 自立门户以 nums[i] 开头形成子序列，这种浅情况就是 nums[i]
+
+基于贪心的思想，也可以统一成一个式子 max(dp[i-1], 0) + nums[i]
+
+接下来，我们考虑环。如果有环，那么最大子序和，要么就和普通的最大子序和一样只是普通的一段子序列，要么就是首尾两段加起来的和最大。
+
+因此我们只需要额外考虑如何计算首尾两段的情况。对于这种情况其实等价于计算中间一段“最小子序和”，然后用数组的总和减去“最小子序和”
+就是答案。而求最小子序和和最大子序和基本没有差异，将 max 改为 min 即可。
+
+## 关键点
+
+- 其中一种情况（两段子序和）：转化为 sum(nums) - 最小子序和
+
+## 代码
+
+- 语言支持：Python3
+
+Python3 Code:
+
+```python
+
+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)$
+
+
+
+
+> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。 
+
+力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦~
+
+以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
