JS 的演算法養成之路 | Maximum Subarray

前言

Hi，大家好！我是神 Q 超人。每次想不到有什麼文章可以打的時候就來解解演算法，剛好也可以為未來的面試做準備，實在是一舉兩得 😂。

這次的題目難度是 Easy，但還是偷走我不少時間去苦惱，一起來看看最後怎麼解掉他 🙌。

題目：56. Maximum Subarray

難易度：Easy

問題描述：給定一個陣列，然後找出相鄰元素（最少一個）相加能得到的最大總和。

測試案例：

example1:Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: 6 是由 [4, -1, 2, 1,] 加起來得到的，是相鄰元素相加能得到的最大總和。

一開始想的很單純，就是去讀陣列裡的所有元素，然後一個一個相加，如果「這一次的加總」比「上一次紀錄的加總」大就更新最大加總，解法大概是這樣子：

var maxSubArray = function(nums) {
   // 「最大加總」和「目前加總」預設 Array 第一個值
  const maxSum = currentSum = nums[0];
 
  for(let i = 1; i <= nums.length; i += 1) {
    currentSum += nums[i]; // 一開始相加
    if (currentSum > maxSum) {
      maxSum = currentSum;  // 新的加總比較大就更新最大加總
    } else {
      /*
        如果沒比較大就把加總的起始元素變成下一個，
        因為保留這個會讓最大值變小，所以加總元素裡不需要有他。
      */
      currentSum = 0;
    }
  }
 
  return maxSum;
};

但是這樣會有問題，假如我的 Input 是 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，那執行的過程會如下：

0. 一開始設定 maxSum 和 currentSum 都是 -2。
1. 第一次迴圈：currentSum 加上 -1 等於 -1，所以會比 maxSum 存著的 -2 還大，於是更新 maxSum，currentSum` 繼續加總。
2. 第二次迴圈：currentSum 加上 -3 等於 -4，而 -4 比 maxSum 目前存著的 -1 還小，因此不更新 maxSum，然後 currentSum 歸 0 從下一個元素開始重新加。
3. 第三次迴圈：currentSum 加上 4 等於 4，所以比目前 maxSum 存著的 -1 還大，所以更新 maxSum，然後讓 currentSum 繼續加總。
4. 第四次迴圈：currentSum 加上 -1 等於 3，比目前 maxSum 中的 4 還小，因此不更新 maxSum，然後 currentSum 歸 0。

這個解法的 Bug 在於第四次迴圈，因為 4 之後所有的元素都不會比 4 還大，所以 currentSum 會一直被歸 0，中斷與下次的加總，導致沒辦法算到 4 + -1 + 3 這個更大的結果，maxSum 也永遠是 4。

後來又多想了一下，決定將判斷的部分改成

因為前面的 currentSum 加上 num[i]，如果不會讓 currentSum 變得比 num[i] 更大，那就不如不要前面那些總計了，直接把 currentSum 改成 num[i] 繼續加總，而在 currentSum 每次加總完也都和當前的 maxSum 比較一下，如果比較大的話就更新 maxSum。

所以解法最後如下：

var maxSubArray = function(nums) {
  let currentSum = maxSum = nums[0];

  for(let i = 1; i < nums.length; i += 1) {
    currentSum += nums[i];
    if (currentSum < nums[i]) {
      currentSum = nums[i];
    }

    if (currentSum > maxSum) {
      maxSum = currentSum;
    }
  }

  return maxSum;
};

重點就在於 if(surrentSum < nums[i]) 這一行判斷，如果成立的話就直接把 surrentSum 設定成更大的 nums[i]，接下來就只要一直加下一個元素，然後與 maxSum 比較，比較大的話就更新，比較小的話就不動。

因為只跑一次陣列裡面的所有內容，時間複雜度應該是 O(n)，所以成績算是還不錯：

在這道題目的解釋後面啊，還有附上這麼一句話：

非常耐人尋味的一句話，就像四大天王其實有五個人一樣，不過筆者就沒有繼續研究它了，覺得能夠解出來已經相當滿足 😂，如果各位有更好或更棒的方式，請留言和我分享 🙌。

如果文章中有任何問題，也請告知我，我在迅速修正，非常感謝！