Problem: 918. 环形子数组的最大和

👨‍🏫 参考题解

⏰ 时间复杂度：$O(n)$
🌎 空间复杂度：$O(1)$

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int maxSum = Integer.MIN_VALUE; // 最大子数组和，不能为空
        int minSum = 0; // 最小子数组和，可以为空
        //在非循环数组下，max 是当前得出的最大子数组和，min 是最小子数组和
        int max = 0, min = 0, sum = 0;// sum 是总和
        for (int x : nums) {
            // 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和
            max = Math.max(max, 0) + x;
            maxSum = Math.max(maxSum, max);
            // 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和
            min = Math.min(min, 0) + x;
            minSum = Math.min(minSum, min);
            sum += x;
        }
        // sum == minSum 时表明最小子数组是整个数组（数组元素全是负数的情况）
        // sum - minSum 为跨越边界的最大子数组和
        return sum == minSum ? maxSum : Math.max(maxSum, sum - minSum);
    }
}