Leetcode 53. Maximum Subarray 題解

目錄：

百日刷百題 刷題進大廠——Leetcode高頻題精講合集

上一篇：

Leetcode 863。 All Nodes Distance K in Binary Tree 題解

| 下一篇：

Leetcode 1143。 Longest Common Subsequence 題解

類別：陣列(

Array）

題目：

53。 Maximum Subarray

思路1：

先不考慮Follow up，按最原始的思路來解。在一個有正負數的陣列中求連續和，我們還是畫一畫看看。

第一個橫軸表示0，每個在0上下方的點分別表示陣列中大於或小於0的數字。第二個橫軸表示每次從0開始累計的和（Sum）。很容易看到，由於是要找連續子陣列的和，假如掃描到陣列中的某一個元素i的時候，前面的0到i-1個數字和要麼小於等於0，要麼大於0。如果大於0，我們在Sum上繼續加現在的第i個數字，無論第i個數字是正數還是負數，新的Sum結果肯定都比第i個數字本身大。相反，如果0到i-1個數字的Sum小於等於0，算上第i個數字的Sum最佳結果也就是第i個數字本身，這時我們可以忽略掉前面的Sum，從i開始從新累加。與此同時每次Sum值變動時，我們比較一下到目前為止已經發現的最大的Sum值，如果當前Sum更大，則更新它。

程式碼實現1（Swift版本）：

複雜度分析1：

這種解法我們只迴圈了一次陣列，因此時間複雜度為O（N）。

思路2：

現在考慮Follow up。題目要求用分治法（Divide and conquer）來解。我們隨機選擇一個點mid。

從mid開始分治看看如何把問題規模變小。首先很明顯的是我們把整個陣列分成0到mid這一部分和mid到n-1這一部分，我們可以先求左右兩個更小規模的最大和（maxSum），並選取其中較大的一個作為備選方案。還有第三種情況是什麼呢，就是最大和包含了mid，如上圖中的3，我們只需要從mid出發，分別向當前陣列的兩邊延伸，延伸的過程中不斷往Sum中加上每一個遇到的數字，同時記錄下遇到的最大值，即可得到從mid出發往左右分別得到的maxSum，兩者相加得到上圖中情況3的最大和。最後比較三種情況的最大和中最大的那個就是這個陣列的最大和。同樣的方法應用在每個左右子陣列中，一直遞迴到只有一個元素的陣列。我們來看看如何實現。

程式碼實現2（Swift版本）：

複雜度分析2：

分治法是一個遞迴的方法，因為每次把輸入陣列的規模一分為二，一般來說可以畫出一顆二叉樹的形狀來分析呼叫次數。我們假設有N個元素。

一層層一分為二，一共可以分出Log（N）層。每層的每一個子陣列由於要進行上面思路2中提到的第三種情況的掃描，也就等於每一層我們都掃描了所有數字一次即O（N），那麼彙總起來我們進行了Log（N）次O（N）級別的操作，總的時間複雜度就是O（NLog（N））。