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:

1
2
3

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。
接下來的流程，讀者可以嘗試自己操作一遍再對照一下。

1
2
3
4

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

1
2
3
4

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

1
2

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

1
2
3

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

1
2
3

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

1
2

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

1
2

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學演算法，我們下次見囉，掰~