iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 14
0
自我挑戰組

[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ系列 第 14

[LeetCode with JavaScript] Day 14: Maximum Subarray

觀前提醒:

  1. 我預設大家已經先思考並分析過題目,沒啥想法才開始 google 找解題靈感。若無,建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法
  2. 承上,既然已經有思考過了,那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了,那我可能解題想法 & 心得的部分就不會寫太多,免得干擾你的思考。
  3. 所有解法都是已經取得系統的 Accepted,但或許不是最優解法,請多包涵。
  4. 若對於解法不太懂,可以嘗試用 Chrome 的 debugger 來試跑看看 (教學文)
  5. 最後,歡迎在下面留言指教~教學相長才會進步歐~/images/emoticon/emoticon41.gif

題目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-2147483647]
Output: -2147483647

Constraints:

  • 1 <= nums.length <= 2 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

解題想法

這題,算是整個CS領域中,相當經典的題目。實作方法有很多種,分別有暴力法、Divide and Conquer和Kadane's演算法(Dynamic Programming)。那小弟在這邊,還是推薦 Jay Kadane教授的Kadane算法歐~

Kadane's演算法為Dynamic Programming(動態規劃)方式,概念上其實是很直覺的思考:

  • 如果目前元素陣列和 + 新數字大於新數字本身,則把新數字放進目前元素陣列和中。反之則以新數字當作新的開頭。
  • 然後記錄下目前元素陣列和大於最大值時,則把目前元素陣列賦值給最大值。

大家聽到這邊,一定會覺得說,X我到底看了三小...哈哈哈。
別緊張,且聽我娓娓道來~請參考下面兩個 case 與解說

img
我們這樣定義:

  • case 1 : 藍色框框為目前元素陣列和 = 0 ,"5"為新數字。
    當藍色框框,變成紅色框框,代表我們的陣列和擴充,把5給放進去,那這時的元素陣列和會從 0 ,躍升成 5 。那就代表這個最大子陣列,應該要繼續擴充下去~

  • case 2 : 藍色框框為目前元素陣列和 = 5 ,"-2"為新數字。
    當藍色框框,變成紅色框框,代表我們的陣列和擴充,把 -2 給放進去,那這時的元素陣列和會從 5 ,降為 3 。那就代表這個最大子陣列,應該要從-2開始,當作新的起點,繼續運算下去。

CODE

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  let max = -Infinity;
  let currentSum = 0;
  for (let i = 0; i < nums.length; i++) {
  //如果目前元素陣列和 + 新數字大於新數字本身,則把新數字放進目前元素陣列和中。反之則以新數字當作新的開頭。
    if (nums[i] + currentSum > nums[i]) {
      currentSum += nums[i];
    } else {
      // 以這個元素當作新的開頭。
      currentSum = nums[i];
    }
    // 若 currentSum 大於 max時,則把 currentSum 賦值給 max。
    if (currentSum > max) {
      max = currentSum;
    }
  }
  return max;
};

心得

這題雖然是 easy,暴力法也是可以解得出來。但當我看到 Jay Kadane 教授的算法後,覺得真的是太酷了,真的很想把它分享給大家,這真的是很優雅的解法,太神喇~/images/emoticon/emoticon12.gif


謝謝大家的收看,LeetCode 小學堂我們下次見~/images/emoticon/emoticon29.gif


上一篇
[LeetCode with JavaScript] Day 13: Valid Parentheses
下一篇
[LeetCode with JavaScript] Day 15: Climbing Stairs
系列文
[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言