LeetCode——918. 環形子數組的最大和（JavaScript)

給定一個由整數數組 A 表示的環形數組 C，求 C 的非空子數組的最大可能和。

在此處，環形數組意味着數組的末端将會與開頭相連呈環狀。（形式上，當0 <= i < A.length 時 C[i] = A[i]，而當 i >= 0 時 C[i+A.length] = C[i]）

此外，子數組最多隻能包含固定緩沖區 A 中的每個元素一次。（形式上，對于子數組 C[i], C[i+1], …, C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）

示例 1：

輸入：[1,-2,3,-2]
輸出：3
解釋：從子數組 [3] 得到最大和 3
           

示例 2：

輸入：[5,-3,5]
輸出：10
解釋：從子數組 [5,5] 得到最大和 5 + 5 = 10
           

示例3：

輸入：[3,-1,2,-1]
輸出：4
解釋：從子數組 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4
           

示例4：

輸入：[3,-2,2,-3]
輸出：3
解釋：從子數組 [3] 和 [3,-2,2] 都可以得到最大和 3
           

示例5：

輸入：[-2,-3,-1]
輸出：-1
解釋：從子數組 [-1] 得到最大和 -1
           

提示：

1. -30000 <= A[i] <= 30000
2. 1 <= A.length <= 30000

思路：

擁有最大和的子數組有以下兩種情況：

1. 子數組沒有越界，不需要發生末端和開頭的環形，就像上面的示例1、示例4
2. 子數組有越界，子數組包含末端和開頭，但中間部分元素不包含，例如示例2.

對于第一種情況，其實就是求普通數組的連續子數組的最大和，使用兩個變量，curr 和 sum，分别表示加上目前元素後的和，以及，最終的最大和。

周遊元素，将 curr 與 0 之間的最大值加上 目前元素，若大于sum，更新sum。

let curr = Number.MIN_SAFE_INTEGER
let sum = Nunber.MIN_SAFE_INTEGER
for (let a of A) {
	curr = Math.max(curr, 0) + a
	sum = Math.max(curr, sum)
}
           

對于第二種情況，可以求出這個普通數組的連續子數組的最小和，然後剩下的兩段元素的和就是最大和了。

let curr = Number.MAX_SAFE_INTEGER
let sum = Nunber.MAX_SAFE_INTEGER
let total = 0
for (let a of A) {
	curr = Math.min(curr, 0) + a
	sum = Math.min(curr, sum)
	total += a
}
sum = total - sum
           

同時求最大和與最小和，若最大和小于0，說明所有元素都小于0，傳回這個最大和即可，否則，傳回最大和與（total - 最小和）之間的最大值。

最終代碼：

/**
 * @param {number[]} A
 * @return {number}
 */
var maxSubarraySumCircular = function(A) {
  let minCurrSum = Number.MAX_SAFE_INTEGER,
      minFinalSum = Number.MAX_SAFE_INTEGER,
      total = 0,
      maxCurrSum = Number.MIN_SAFE_INTEGER,
      maxFinalSum = Number.MIN_SAFE_INTEGER;
  for (let a of A) {
    minCurrSum = Math.min(minCurrSum, 0) + a
    minFinalSum = Math.min(minCurrSum, minFinalSum)
    maxCurrSum = Math.max(maxCurrSum, 0) + a
    maxFinalSum = Math.max(maxCurrSum, maxFinalSum)
    total += a
  }
  return maxFinalSum > 0 ? Math.max(maxFinalSum, total - minFinalSum) : maxFinalSum
};