這周主要實現了LeetCode Algorithms中的Divide-And-Conquer的題目，這里選擇二道題來分析，分別是Maximum Subarray(easy)、Merge k Sorted Lists(Hard)。

一、Maximum Subarray

題目描述：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.

分析：這個題最開始的做法是采用了分治法，參考《算法分析》4.1的最大子數組問題?？紤]最大值會出現的三種情況，即將數組分為三個部分，最大子序列可能會是前半部分或后半部分或者是跨越了中點的序列中，比如S1max$S1_{max}$、S2max$S2_{max}$、S3max$S3_{max}$。

對于S2max$S2_{max}$對應的序列，從中間點開始，往左部分的序列和是左邊序列的最大序列和，往右部分的序列亦然。這樣的話可以直接從中點分別往左和右開始計算，得出兩邊的最大序列和，那么跨越中點可以得到的最大序列和就是兩邊序列和的累加；

對于S1max$S1_{max}$、S3max$S3_{max}$對應的序列，可以直接遞歸調用上述分割過程，對左數組（A0$A_0$……Amid$A_{mid}$）和右數組（Amid$A_{mid}$……An$A_{n}$）和跨越中點的序列分別求其最大子序列的和；

　　最終返回三種計算中的最大的序列和即可。這樣的做法的時間復雜度是T(n)=2T(n2)+O(n)$T(n) = 2T(/frac{n}{2})+O(n)$，套用大師定理即可得到T(n)=O(nlogn)$T(n)=O(n/log n)$。

　　分治法的結果如下：

　　但是，這樣的分治法，其實是很麻煩的，RunTime為13ms?？梢灾苯油ㄟ^優化把算法的復雜度降到O(n)$O(n)$。

　　對于數組，我們可以這樣考慮：

　　我們定義SUMnow$SUM_{now}$為當前的序列的和，SUMmax$SUM_{max}$是已經讀取到的序列中可以計算出的最大序列和?，F在考慮加上下一個元素之后的新的SUMnow$SUM_{now}$:

　　代碼的過程可以寫作下面的形式：

　　可以看出此時的算法的復雜度只有O(n)$O(n)$了，通過提交發現RunTime也變為了9ms，得到了很大的提升。 　　

二、Merge k Sorted Lists

題目描述： Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Subscribe to see which companies asked this question.

分析：其實這個題的難度并不大，可以直接通過歸并排序完成。最主要的就是了解歸并排序的流程。 　　 　　歸并排序是典型的分治模式的算法，它主要是通過把n$n$個元素分成各有n2$/frac{n}{2}$個元素的兩個子序列，排序兩個子序列，最后合并兩個子序列。而n2$/frac{n}{2}$個元素還可以分為兩個元素數為n4$/frac{n}{4}$的子序列，重復進行排序和合并，即為歸并排序。歸并排序的關鍵是“合并”。 　　 　　如下圖所示，這里我們假設某一段序列長度為10，我們將其對半分成兩個子序列后對其分別排序，之后將兩個序列合并。每次都取出兩個序列較小的一個元素，被選擇的序列下一次被用來對比的就是下一位元素。這樣子不斷的對比選擇，就能把兩個子序列合并了。

　　題目要求的是對多條鏈表的合并，需要注意的是鏈表的長度都是不一致，所以需要在合并過程時判斷是否應該繼續用某一序列的下一位來判斷取值。

　　代碼如下所示：

　　直接使用歸并排序，每次都選擇分割兩個序列，算法負責度可以寫作T(n)=2T(n/2)+O(n)$T(n) = 2T(n/2)+O(n)$，即T(n)=O(nlogn)$T(n) = O(n/log n)$。

　　總結：其實這周實現的算法都不是很難，但是可能我更多的時間都花在了怎么去優化它們了，最開始總是有先入為主的想法，分治一定會比較快，但其實不盡然（當然也有可能是我想的分治法比較麻煩==）?？傊?，我覺得這周選擇的題目不僅剛好把課上學到的分治法的分析思想用上了，也讓我學著去思考優化的問題，感覺收獲頗多，接下來還是要好好刷題^^