iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 8
1
Software Development

從LeetCode學演算法系列 第 8

[Day 8] 從LeetCode學演算法 - 0053. Maximum Subarray (Easy)

目標:
這題主要目的在於學習一個常見的演算法:動態規劃(Dynamic Programming)。

原題:

Question:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
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.

分析/解題:
題目給定一個整數陣列,要求找到其中一個連續的子陣列,
這個子陣列的和是所有子陣列中最大的,並且回傳該總和值。

這題如果以暴力法來解決的話,我們可以拿到的總連續子陣列數是
N+(N-1)+(N-2)+…+1,每個子陣列中的計算下一組和(如[-2] -> [-2,1]),
都只需一個加法,故時間複雜度會是O(N²)。

但......感覺很浪費(?)
我們先思考一個問題:
「假設我知道nums中1到i-1的最大子陣列和,
有沒有辦法知道1到i的最大子陣列和呢?」
我們討論1到i的最大子陣列和,應該分兩種情況:
a. 這個子陣列包括index i
b. 這個子陣列不包括index i
如果是b的話,那答案其實就是1到i-1的最大子陣列和
但如果是a的話,我們好像還需要一些條件?
什麼條件呢?就是1到i-1中,包含i-1元素的最大子陣列和。
因為如果是前面所提到的a狀況的話,
那麼1到i的最大連續子陣列,就必須從i->i-1連回去才行(或乾脆是只有i)。

所以這麼一來,條件就比較清楚了,我們會需要的有:

  1. 到現在為止包含當前這個元素的最大子陣列和,我們命名為curr(current)
  2. 到目前為止的最大子陣列和,我們命名為res(result)

那麼我們就以範例的[-2,1,-3,4,-1,2,1,-5,4]來操作看看。
該怎麼決定curr跟res的初始值呢?因為一開始只有一個值,
所以curr和res應該都等於nums[0]=-2才對。
所以一開始我們將curr和res都設為-2,接下來由i=1開始,
一路往下到最後一個結束。

i=1: [-2,1,-3,4,-1,2,1,-5,4]
按我們的定義,curr應該是-2+1和1中較大的值,
我們可以先將curr加上nums[1],
接下來檢查curr小於0,或者curr<nums[1]
就表示其實我們只要取nums[1]就好。
(註1: 表示兩者的正負號為(-, -), (-, +),不論如何
前面那部分貢獻均是負的
)
(註2: 也可以拆成別的形式或調換順序,但先判斷<0的計算速度會比較快)
(註3: 後面程式碼Java和Python的判斷方式就不同,可自行依喜好決定使用)
所以新的curr為1, 接著再比較得知curr<res,故res也要改為1。
接下來的流程,讀者可以嘗試自己操作一遍再對照一下。

i=2: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 1 + -3 = -2 < 0
-> curr = -3
-> res = 1

i=3: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = -3 + 4 = 1 < 4
-> curr = 4
-> res = 4

i=4: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 4 + -1 = 3 > -1

i=5: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 3 + 2 = 5 > 2
-> res = 5

i=6: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 5 + 1 = 6 > 1
-> res = 6

i=7: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 6 + -5 = 1 > -5

i=8: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 1 + 4 = 5 > 4

所以最後我們得到res = 6,再回傳即可。

這個解法第一次並不是很容易上手,而且並非相當直觀的方式,
但它常常可以在特別的地方有效地解決問題。
適用於這類型的解法的問題會有一個特性:
「N=i+1時的解,通常和N=i時的解以及第i+1的值有關連性」
(也有可能跟更前面幾個值同時有關連性)
而我們通常很難直觀地直接用簡單的方式去算出N=i+1的解,
所以會依靠其本身和前面的連動關係
讓答案像堆積木一樣,從i=0開始堆到最後面得到最終的答案。

有些問題可能未必是一層一層疊上去,
也有可能是把一個大問題拆成數個小問題,
最後將其組合起來得到大問題的答案。
但通常我們最常見的形式還是如上面那樣子按順序堆疊的。

上面這樣子形式的解題方法,
被稱之為動態規劃(Dynamic Programming),或者也常簡稱為DP。
每個動態規劃的問題都會有些不一樣,
但只要抓到其中的連動性,找到從i -> i+1中間的關聯,
就可以順利解開題目。

Java:

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int curr = nums[0];
        for(int i = 1; i < nums.length; i++) {
            curr += nums[i];
            if (curr < 0 || nums[i] > curr)
                curr = nums[i];
            if (res < curr)
                res = curr;
        }
        return res;        
    }
}

Python:

class Solution:
    def maxSubArray(self, nums: 'List[int]') -> 'int':
        l = len(nums)
        if l == 0: return 0
        res = now = nums[0]
        for i in range(1, l):
            if now > 0:
                now += nums[i]
            else:
                now = nums[i]
            
            if now > res:
                res = now
        return res

面試實際可能會遇到的問題:
「時間/空間複雜度?」
(O(N), O(1))

「如果不使用DP是否有O(N)解?」
(可以使用分治法,請參見 LeetCode這篇討論 底下的回應)
從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0067. Add Binary (Easy)


上一篇
[Day 7] 從LeetCode學演算法 - 0035. Search Insert Position (Easy)
下一篇
[Day 9] 從LeetCode學演算法 - 0067. Add Binary (Easy)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言