题目描述

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

提示：

• n == nums.length
• 1 <= n <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104

测试用例

示例 1：

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

示例 2：

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

示例 3：

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

思路

参考代码注释

代码实现

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入nums数组:");
const nums = readline()
  .split(",")
  .map((item) => parseInt(item));

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubarraySumCircular = function (nums) {
  // 环形子数组最大
  // 两种情况

  // 1. 子数组没有用到环形，相当于计算最大非空子数组和
  // 2. 子数组用到了环形，—— 相当于数组的总和 - 非空子数组和最大 —— 即求最小非空子数组和
  // 最后返回两种情况的最大值即可

  // 注意特殊情况，最小非空子数组就是整个数组 —— 那我们就不考虑情况二 —— 直接返回情况一

  // 5 -9 4 4 -9 5
  let max1 = Number.MIN_SAFE_INTEGER; // 情况1
  let maxChild = 0;
  let min2 = 0; // 情况2
  let minChild = 0;
  let sum = 0;

  for (let i = 0; i < nums.length; i++) {
    // 求最大非空子数组和 —— 以nums[i - 1]结尾的子数组选或不选
    // Math.max(maxChild, 0)就是如果有前边的是负数了，那就不选前边的元素了
    maxChild = Math.max(maxChild, 0) + nums[i];
    max1 = Math.max(max1, maxChild);
    minChild = Math.min(minChild, 0) + nums[i];
    min2 = Math.min(min2, minChild);
    sum += nums[i];
  }

  return sum === min2 ? max1 : Math.max(max1, sum - min2);
};

const res = maxSubarraySumCircular(nums);
console.log("结果为: ", res);

/* 
  请输入nums数组:
  1,-2,3,-2
  结果为:  3

  请输入nums数组:
  5,-3,5
  结果为:  10
  
  请输入nums数组:
  3,-2,2,-3
  结果为:  3
*/