從LeetCode學演算法 - 7 Dynamic Programming (1)

0053. Maximum Subarray (Easy)

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

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:

Python:

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

「如果不使用DP是否有O(N)解？」 (可以使用分治法，請參見 LeetCode這篇討論 底下的回應)

從LeetCode學演算法，我們下次見囉，掰~

如果你／妳覺得這篇文章不錯，請給我5個拍手，並且給我5個Like。(點開SHOW EMBED!)
如果你／妳非常喜歡這篇文章，可以按著拍手直到50下。
也請記得「Follow」我，隨時收看最新的文章。