LeetCode： Maximum Subarray

Question

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]

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6

Example 2:

Input: nums = [1]

Output: 1

Solution

要解題之前，需要先了解什麼是 Kadane’s Algorithm？

“Kadane 算法掃描一次整個數列的所有數值，在每一個掃描點計算以該點數值為結束點的子數列的最大和（正數和）。該子數列由兩部分組成：以前一個位置為結束點的最大子數列、該位置的數值。因為該算法用到了「最佳子結構」（以每個位置為終點的最大子數列都是基於其前一位置的最大子數列計算得出），該算法可看成動態規劃的一個例子。” ― 維基百科 ―

def max_sub_array(nums)
  # 累計陣列中子結構之和
  max_here = 0

  # 最佳子結構之正數和，暫時以陣列中第一個元素為值
  max_so_far = nums[0]

  # 用 each 方法跑每一個元素
  (0...nums.size).each do |i|
    # 累計總和 = 原有的累計值 + 當下輪到的元素值
    max_here = max_here + nums[i]

    # 如果『當下輪到的元素值』比『累計總和』大
    if max_here < nums[i]
      # 『累計總和』會被『當下輪到的元素值』取代
      max_here = nums[i]
    end

    # 如果『累計總和』比『最佳子結構之正數和』大
    if max_so_far < max_here
      #『最佳子結構之正數和』就會被『累計總和』取代
      max_so_far = max_here
    end
  end

  # 跑完全部元素之後，再回傳『最佳子結構之正數和』
  max_so_far
end

以第一個範例來說：

nums = [-2,1,-3,4,-1,2,1]

以 Dynamic Programming 來規劃，建立兩個變數：max_here 和 max_so_far

max_here： 累計『前一個位置為結束點的子數列總和』＋「該位置的數值」

max_so_far： 它將與 max_here 做比對，再決定『該最佳子結構』的總和是否要加入「該位置的數值」

＃ 從 -2 開始計算， max_here = 0, max_so_far = 0
[-2]

＃ 換到元素 1 開始計算， max_here = 1, max_so_far = 1
[-2,1]

＃ 換到元素 -3 開始計算， max_here = -2, max_so_far = 1
[-2,1,-3]
max_here = 1 + -3 = -2
if -2 < -3
end
if 1 < -2
end

＃ 換到元素 4 開始計算， max_here = 4, max_so_far = 4
[-2,1,-3,4]
max_here = -2 + 4 = 2
if 2 < 4
  max_here = 4
end
if 1 < 4
  max_so_far = 4
end

＃ 換到元素 -1 開始計算， max_here = 3, max_so_far = 4
[-2,1,-3,4,-1]
max_here = 4 + -1 = 3
if 3 < -1
end
if 4 < 3
end

＃ 換到元素 2 開始計算， max_here = 5, max_so_far = 5
[-2,1,-3,4,-1,2]
max_here = 3 + 2 = 5
if 5 < 2
end
if 4 < 5
  max_so_far = 5
end

＃ 換到元素 1 開始計算， max_here = 6, max_so_far = 6
[-2,1,-3,4,-1,2,1]
max_here = 5 + 1 = 6
if 6 < 1
end
if 5 < 6
  max_so_far = 6
end