LeetCode-918. 环形子数组的最大和

给定一个长度为 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

示例

示例一

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

示例二

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

示例三

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

方法一 利用maxSum和minSum来计算

由题可知，最大连续子数组的位置有两种情况
情况一：在数组内，不成环
情况二：在数组两端成环
对于情况一，可以参考leetcode 53题最大子数组和

下面分析第二种情况
可知数组的总和是一定的，如果存在最大子数组，那么剩余部分的数字总和一定是最小的，我们用反证法来证明：
设数组总和为sum，最大字数和为max，剩余部分和为other，那么就有个

max + other = sum
1

如果other不是最小连续子数组，那么存在最小连续子数组，其和为min，其中：

min < other
1

那么其他剩余的部分的和一定大于max：

sum - min > sum - other 
1

此时max就不是最大连续子数组

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int iMax = Integer.MIN_VALUE;
        int iMin = Integer.MAX_VALUE;
        int iMaxSum = 0;
        int iMinSum = 0;
        int total = 0;
        for(int num : nums)
        {
            iMaxSum = Math.max(iMaxSum + num,num);
            iMax = Math.max(iMaxSum,iMax);
            iMinSum = Math.min(iMinSum + num,num);
            iMin = Math.min(iMinSum,iMin);
            total += num;
        }
        return iMax > 0 ? Math.max(iMax,total-iMin) : iMax;
        // return Math.max(iMax,total-iMin);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意return为什么不是Math.max(iMax,total-iMin);
因为如果数组中全部都是负数，那么imax也是负数
此时min = total ，而 total -total = 0
所以不能返回min，而是返回imax