Leetcode-Algorithm-Divide and Conquer-53

例子： 給定數組[-2, 1, -3, 4, -1, 2, 1, -5, 4]，那么和最大的連續子數組是[4, -1, 2, 1]，和為6。

題解：

方法1：（動態規劃） 迭代數組中的每一個數，把它們逐一加起來。把最終結果的和設為res，迭代過程的和設為sum。令res等于第一個元素，每加一個數，可能出出現3種情況：①sum增大；當sum大于res時，由于是連續元素相加得到的sum，所以符合連續子數組最大和，因此令res等于sum；②sum減少，小于res，但sum仍大于0，保留res的取值，由于sum大于0，進入下一次迭代加上下一個元素后有可能大于res，因此跳到下一個迭代；③sum減少到小于0，無論后面加多少個元素，都會比后面元素之和要少，因此重新計算sum，令sum等于0。保留res表示之前連續元素的最大和。在每次迭代中對以上情況做相應處理，最后的res就是答案。

代碼：

分析： 由于只需迭代一次數組元素，因此時間復雜度為O(n)$O(n)$。

方法2：（分治法） 首先，令連續子數組的最大和為res，那么和最大的連續子數組的位置有三種可能： ①在數組的左半部分，由于和是最大的，所有比右半部分以及中央部分元素之和要大。 ②在數組的右半部分，同理，比左半部分以及中間部分元素之和要大。 ③位于數組的中間部位，那么通過從數組中央元素往數組兩頭計算的最大和leftmax+rightmax（要求逐一相加元素），會比左右兩半部分的連續子數組最大和leftres、rightres都大。 同理，當連續子數組在數組的左右兩部分時，可以繼續上述步驟。

代碼：

分析： 由上述分析可知，輸入規模在每次遞歸都減半，而且需要計算兩個部分，對兩部分的合并處理需要O(n)$O(n)$步，因此，可得下面的公式：T(n)=2T(n/2)+O(n) $$T(n)=2T(n/2)+O(n)$$ 所以通過大師定理計算得時間復雜度為：O(nlogn) $$O(nlogn)$$