题目大意：
环形子数组的最大和
给定一个由整数数组 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] <= 300001 <= A.length <= 30000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=918
解题思路分析：
如果不考虑环状数组的话，本题难度并不大，有关求最大子串和的问题我们在之前的文章中多次提到过，这里再简单重复一下，我们定义两个变量sum和maxSum，分别代表当前区间和以及全局最大区间和，接下来遍历数组中每一个数字num，如果num > num+sum，说明当前数字在不累加到num的情况下更大一些，因此我们可以舍弃之前的sum，将sum设置为当前num。继续向下遍历，反之将num累加至sum。每循环完一个数字后，我们都要使用当前的sum去更新全局最大值maxSum，当循环结束后，maxSum即是我们要求的最大子串和。另外求最小子串和也可以使用相同的思路。
再回到本题，由于题目说明数组可以首尾相接，即可以看成一个圆环，这样题目虽然变得稍微复杂，但是也依旧可以使用上文提到的方法来解题。试想，最终的答案一定是以下两种情况：
- 最大子数组是原数组的子数组或本身。
- 最大子数组是由原数组的前缀子数组以及后缀子数组组合而成。
对于第一种情况，我们使用上文提到的查找最大子串和的方式就可轻松找到。而对于第二种情况，换一个思路，实际上可以在原数组中找到一个最小子串和，然后再使用原数组的总和减去这个最小子串和，即可得到一个最大的环形子串。换句话说，这个最小子串左右两边剩下的部分即是第2种情况的答案。
最终，两种情况的最大值即是本题的解。
实现代码：
public int maxSubarraySumCircular(int[] A) {
// 第一种情况
int sum=0; // 区间和
int max=Integer.MIN_VALUE; // 最大区间和
for(int n : A){ // 循环每一个数字
// 如果当前数字加上sum还没有本身大，将当前数字设置为sum
if(n>n+sum) sum=n;
// 反之将当前数字累加至sum
else sum+=n;
// 更新全局最大sum
max=Math.max(max,sum);
}
// 第二种情况
sum=0; // 区间和
int allSum=0; // 数组总和
int min=Integer.MAX_VALUE; // 最小区间和
for(int n : A){ // 循环每一个数字
allSum+=n; // 累加数组总和
// 如果当前数字加上sum还没有本身小，将当前数字设置为sum
if(n<n+sum) sum=n;
// 反之将当前数字累加至sum
else sum+=n;
// 更新全局最小sum
min=Math.min(min,sum);
}
// 如果最小值等于数组总和（数组中全是负数），返回max
if(min==allSum) return max;
// 返回两种情况的最大值
return Math.max(max, allSum-min);
}本题解法执行时间为2ms。
Runtime: 2 ms, faster than 100.00% of Java online submissions for Maximum Sum Circular Subarray.
Memory Usage: 45.8 MB, less than 10.00% of Java online submissions for Maximum Sum Circular Subarray.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-918-maximum-sum-circular-subarray-解题思路分析/