蛮力法 分治法 动态规划求最大字段和

/*蛮力法 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<n;i++){ int th

#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