題目連結：
題目意譯：
給定一整數陣列 nums，找到其最大連續子陣列（至少有一個元素）之和，並回傳該總和。
進階：
如果你想出了 O(n) 解法，試著利用分治法（Divide and Conquer）解這題，而該解法較不明顯。
範例測資：
範例：
輸入： [-2,1,-3,4,-1,2,1,-5,4],
輸出： 6
解釋： [4,-1,2,1] has the largest sum = 6.
解題思維：
O(n) 的做法即這題的解法（的前半部分）。
至於進階提及的分治法，則是以下：
將目前的陣列分作兩半，遞迴左半邊以及右半邊各自的最大連續子陣列之和。停止條件很簡單，切到剩一個元素的時候直接回傳該元素值。
當求出左右兩邊各自的最大總和 L 、 R 之後，還會有一種情況我們沒有考慮到，也就是橫跨左右兩邊的連續最大。而該值可以藉由從中間開始，往左、往右找最長的總和非遞減數列。而該值 M 就是那兩個數列之和。
所以目前陣列的最大即是 L 、 M 、 R 中的最大值。
而這個方式為 O(n log n)。不過其實分治法一樣可以做到 O(n) ，待補。
（2021 / 07 / 14 更新）
可以看到我們的癥結點是在橫跨左右兩半的子陣列。不過仔細觀察後，可以看到它的內容必定是左側的最大後綴和以及右側的最大前綴和所合併而成。
而實際上，一個陣列的最大後綴和、最大前綴和可以在分治的時候順便求得：
假設我們現在要求
最大連續和 M、
最大前綴和 P、
最大後綴和 S、
陣列總和 T、
這四個值。
則對於陣列 nums 我們將其切一半：
設左邊的解為 ML 、 PL 、 SL 、 和 TL
設右邊的解為 MR 、 PR 、 SR 、 和 TR
則我們可以合併左右兩半的解得到
M = max(ML, MR, SL + PR)
P = max(PL, TL + PR)
S = max(SR, TR + SL)
T = TL + TR
而當陣列只有一個元素時，M = P = S = T = 該元素值。
因此時間複雜度 T(n) = 2T(n ÷ 2) + O(1)。根據主定理（Master Theorem），可以看到 T(n) = O(n)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
