编辑代码

#include <stdio.h>

int maxSubSum(int arr[], int left, int right){
    int sum = 0, i;
    if(left >= right){
        if(arr[left]>0){
            sum = arr[left];
        }else{
            sum = 0;
        }
    }else{
        int center = (left+right)/2;
        int leftSum = maxSubSum(arr, left, center);
        int rightSum = maxSubSum(arr, center+1,right);
        int s1 = 0, lefts = 0;
        for(i = center; i >= left; i--){
            lefts = lefts + arr[i];
            if(lefts > s1){
                s1 = lefts;
            }
        }
        int s2 = 0, rights = 0;
        for(i = center+1; i <= right; i++){
            rights = rights + arr[i];
            if(rights > s2){
                s2 = rights;
            }
        }
        sum = s1+s2;
        if(sum < leftSum){
            sum = leftSum;
        }
        if(sum < rightSum){
            sum = rightSum;
        }
    }
    printf("%d-%d,sum=%d\n",left,right,sum);
    return sum;
}
int main () {
    //JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。 
    printf("算法-分治法-最大字段和!     - c.jsrun.net.\n");
    int arr[] = {-2,11,-4,13,-5,-2};
    int size = sizeof(arr)/sizeof(arr[0]);
    printf("0\t1\t2\t3\t4\t5\n-2\t11\t-4\t13\t-5\t-2\n");
    printf("结果：%d", maxSubSum(arr, 0, size));
    return 0;
}