[LeetCode] 53. Maximum Subarray

轉自LeetCode

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

<Solution>

這題希望我們可以用 O(n) 以及 divide and conquer 兩種做法來解

先來看 O(n) 的解法

仔細觀察一下，用題目給的例子 [-2, 1, -3, 4, -1, 2, 1, -5, 4]

一開始是 [-2]，sum = -2

增加一個元素 [-2, 1]，sum = -1 < 1

這代表一件事，從 -2 開始的 subarray 的和，不會比從 1 開始的 subarray 的和還要大

因此可以不用再看從 -2 開始的 subarray

例如 : [-2, 1, -3] => sum = -4，[1, -3] => sum = -2

利用這個特性，可以在一次歷遍就完成 => O(n)

code 如下

再來看 divide and conquer 的解法 (參考資料)

時間複雜度會是 O(nlong)

想法如下

• divide : 分左半和右半，以及 left 和 right 中間的 substring，三個部分

• conquer : 比較 leftMax，rightMax，midMax 誰最大

code如下