#include?
#include?

/*蠻力法?n^2
對于數組a[n]其連續的子段有
?以a[0]開始的??{?a[0]?}?{?a[0]a[1]?}{?a[0]a[1]a[2]?}.....共n????個
?以a[1]開始的??{?a[1]?}?{?a[1]a[2]?}{?a[1]a[2]a[3]?}.....共n-1個
?...
以a[n]開始的，{?a[n]?}共1個
*/
int?MaxSum_ManLi（int?arr[]int?n）{
????int?sum=0;
????int?i=0;
????int?j=0;
????for（i=0;i????????int?thisSum=0;
????????for（j=i;j????????????thisSum?+=?arr[j];
????????????if（thisSum>sum）{
????????????????sum=thisSum;
????????????}
????????}
????}
????return?sum;
}

/*分治法?nlog（n）
分治時，將數組劃分為?[?leftmid?]?和?[?mid+1right?]?兩部分，分別求左側區間的最大子段和，以及右邊區間的最大子段和。
合并時，分為3種情況，
1.左側區間最大子段和大于右側區間最大子段和，且兩個子段不相鄰，選擇左側最大子段和

2.右側區間最大子段和大于左側區間最大子段和，且兩個子段不相鄰，選擇右側最大子段和

3.左右兩個最大子段相鄰，合并子段，返回兩者之和
*/
int?MaxSum_FenZhi（int?a[]int?leftint