918.环形子数组的最大和

环形子数组的最大和

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组的最大可能和。

环形数组意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组最多只能包含固定缓冲区 nums 中的每个元素一次。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• n == nums.length
• 1 <= n <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4

解析

环形数组的最大子数组和有两种情况：

1. 不跨越边界：普通最大子数组和
2. 跨越边界：总和 - 最小子数组和

var maxSubarraySumCircular = function (nums) {
  let maxSum = nums[0],
    curMax = 0;
  let minSum = nums[0],
    curMin = 0;
  let total = 0;

  for (const num of nums) {
    curMax = Math.max(curMax + num, num);
    maxSum = Math.max(maxSum, curMax);

    curMin = Math.min(curMin + num, num);
    minSum = Math.min(minSum, curMin);

    total += num;
  }

  // 如果全是负数，返回 maxSum
  return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
};

时间复杂度 O(n)，空间复杂度 O(1)。