918. 环形子数组的最大和 (opens new window)

1.贪心

分析：环形子数组的最大和只会出现在上述两种情况。仅通过一遍循环同时考虑并计算两种情况的最大和，难度比较大，因此拆解成两个单独的问题，第一遍循环求出情况一结果，第二遍循环求出情况二结果：

• 情况一：贪心，维护一个子数组正数和sum，如果sum小于零则重置为0，相当于更新子数组的起点。
• 情况二：可以发现既然存在这么一个跨界的最大和，那么中间白色连续数组这部分的和一定小于0，因此做法和上面相反，遍历时需要维护一个子数组负数和minsum，每一个minsum都用来更新最大子数组和numSum-minsum，从而确保最终答案一定会被搜索到。

✨分类讨论时，如果发现问题的解在情况A,B,C...都有可能出现，而在代码中同时在多种情况下进行计算的难度比较大，那么不妨尝试单独在情况A下求解得到结果ans1，情况B下求解得到结果ans2...最后再汇总所有结果得到最终答案。

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int res=Integer.MIN_VALUE;
        int sum=0,numSum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            res=Math.max(res,sum);
            if(sum<=0) sum=0;
            numSum+=nums[i];
        }
        int minsum=0;
        boolean isNull=true;
        for(int i=0;i<nums.length;i++){
            minsum+=nums[i];
            if(minsum>0){
                isNull=false;
                minsum=0;
            }
            else{
                if(!isNull)res=Math.max(res,numSum-minsum);
            }
        }
        return res;
    }
}

2.优化

所有环形数组的问题都可以通过将两个nums数组拼接成一个两倍长的数组，转化成上面情况一，当作非环形问题来求解。