繼第 5 天的「15. 3Sum」，今天來解 53 這題！還沒看過第 5 天或再之前天數的朋友，歡迎也去看看~

話不多說，我們開始吧！

基本資訊

• 難度： Medium
• 網址： https://leetcode.com/problems/maximum-subarray/

演算法與資料結構

• Greedy
• Dynamic Programming (DP)

題意

給予一個整數的陣列，回傳出一個子陣列的最大和。

範例

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

子陣列 [4,-1,2,1] 有最大和為 6

思維

題意是需要取最大值，又是連續元素的子陣列，因此我們可以邊走訪，邊取得最大和，捨去較小的和。

分析 DP 的子問題

① 如何取捨子陣列

[-2, 3]

以這個陣列為例，當走訪到 index == 1 的時候 num 為 3

子陣列: [-2]
num: 3

開始處理後，會發現有兩個情境

這時候就會得出，當這個位子之前的和小於當前位置的時候，就可以直接只取當前值

② 保留最大值

在運算過程中，如果沒有保留子陣列之和的最大值，到走訪完畢時的答案就有可能會是錯誤的。

[-2, 3, -1]

例如以這個陣列為例，如果以 ① 的運算，最後得到的值會是 2 ：

因此為了必須要避免這個問題，在走訪的途中，當有需要的時候暫存最大和。

運算結果

當走訪完畢之後，直接回傳走訪過程中暫存的最大即可。

規劃

提前結束條件

• 當給予的陣列為空陣列時，直接回傳 0

主要 Routine

• 陣列走訪以及解決 DP 子問題

程式碼

接著就可以開始寫程式碼了。

初始化時可以以第 0 個元素為初始值，走訪則可以從第 1 個元素開始：

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        guard !nums.isEmpty else { return 0 }

        var current = nums[0]
        var result = nums[0]

        // 主要 routine
        for index in 1..<nums.count {
            let num = nums[index]
            // 1. 處理子問題
            current = max(num, current + num)
            // 2. 暫存當前的最大值
            result = max(result, current)
        }

        return result
    }
}

執行結果

• Runtime: 684 ms (Beats 87.45%)
• Memory: 18.6 MB (Beats 8.23%)

複雜度分析

令 n 為 nums 的總數。

高階函式

也可以用高階函式 reduce 來寫，迴圈內的處理則基本上相同

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var previous = 0
        return nums.reduce(into: nums[0]) { result, num in
            previous = max(num, previous + num)
            result = max(result, previous)
        }
    }
}

執行結果其實大同小異，即使相同的解法多送出幾次甚至還能出現擊敗 100% 的結果 lol

• Runtime: 657 ms (Beats 100%)
• Memory: 18.6 MB (Beats 22.2%)

結語

對自己來說， DP 最重要的其中一件事情是辨識出並看如何處理子問題，而這應該只能靠多做題目來培養判斷力。

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡囉，明天見！