编辑代码

#include <stdio.h>

int Max3(int a,int b,int c)
{
   if(a>=b)
   {
    if(a>=c)
        return a;
    else
        return c;
   }
   else
   {
    if(b>=c)
        return b;
    else
        return c;
   }
}

int MaxSubSum(int *A,int Left,int Right)    //Divide first, then manage them separately.
{    
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBorderSum, MaxRightBorderSum;
    int LeftBorderSum, RightBorderSum;
    int Center, i;

    if(Left==Right) 
    {
        if(A[Left]>0)
            return A[Left];
        else
            return 0;
    }

    Center = (Left + Right) / 2;
    MaxLeftSum = MaxSubSum(A, Left, Center);
    MaxRightSum = MaxSubSum(A, Center + 1, Right);

    MaxLeftBorderSum = 0;
    LeftBorderSum = 0;
    for (i = Center; i >= Left; i--)
    {
        LeftBorderSum += A[i];
        if(LeftBorderSum>MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }

    MaxRightBorderSum = 0;
    RightBorderSum = 0;
    for (i = Center + 1; i <= Right; i++)
    {
        RightBorderSum += A[i];
        if(RightBorderSum>MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }
    return Max3(MaxLeftSum, MaxRightSum, MaxRightBorderSum + MaxLeftBorderSum);
    // This ensures that each recursion is the maximum of the three values.
}

int maxSubArray(int* nums, int numsSize)
{
    return MaxSubseqSum(nums,0,numsSize-1);
}

int main () {
    int arr[10] = {10, 4, -2, 8, 3, -9, 6, 5, -7, 1};
    printf("%d\n", maxSubArray(arr, 10));
	return 0;
}