問題
對一個長度為n的數組，找到連續的子段，使它的和在所有子段中是最大的。
比如3，4，-9，6。他們的最大子段和是7。
解法
A.周遊
O(n)=n^2
B.分治算法
O(N)=N*logN
數組分為Left與Right部分，最大字段和要麼在left，要麼在right，要麼必然包括mid-1與mid+1（這種情況複雜度僅為n，此處mid不代指元素，mid-1與mid+1相鄰），籍此可以遞歸求解。
比如 2，3，-5，6，9可以分為2，3與-5，6，9。左最大子段和5，右最大子段和15，經過3與-5的最大子段和15。三者選最大的15作為結果。
C.動态規劃
将輸入數組描述為a1到an的整數序列，令bj為a1到aj序列中包含aj的最大子段和。由此可以推導，最大字段和是b1到bn的集合中的最大值。
其實動态規劃解法是分治解法的特殊情況，即right的長度為1.此時最大子段和，要麼在左邊，要麼從mid+1開始向左找。
但他們的複雜度并不相同，動态規劃解法複雜度為n。
在解法B中，每次的left和right不同，其實丢失了一部分資訊。而在解法C中，每次left長度都+1，并且上一次的b被保留。
此時最大子段和仍然要麼在左邊，要麼從mid+1向左找，但向左找的過程可以簡化成常數時間（不直接找最大子段和，而是找b，僅僅找經過aj的最大子段和），也就是說不用考慮mid+1以外的項開頭的段。
因為bj的計算一定會經過mid-1或者就是aj本身，是以比較b(j-1)+aj與aj就能确定新的bj（不是新的最大字段和）。為什麼有b(j-1)+aj的式子呢，可以用歸納法推導：j=2時，經過a2的最大和要麼是a2，要麼是a1+a2；j=3時，經過a3的最大和要麼是a3，要麼是b2+a3。可以看出來，無論是a2還是a1+a2，都可以和a3連起來，選擇max(a2,a1+a2)+a3或a3就選擇了最大子段和。