53. 最大子序和

int maxSubArray(int* nums, int numsSize){
    if(numsSize==0)
        return 0;
    if(numsSize==1)
        return nums[0];
    
    return helper(nums,0,numsSize-1);
}
int helper(int *nums,int l,int r)
{
    int mid=(l+r)/2;
    if(l>=r)
        return nums[l];
    int left=helper(nums,l,mid-1);
    int right=helper(nums,mid+1,r);
    
    int lsum=0,rsum=0;
    int max1=0;
    int max2=0;
    int max;
    
    for(int i=mid-1;i>=l;i--)
    {
        lsum+=nums[i]; 
        max1=max1>lsum?max1:lsum;
    }
    for(int j=mid+1;j<=r;j++)
    {
        rsum+=nums[j];
        max2=max2>rsum?max2:rsum;
    }
    max=left>right?left:right;
    return max>(max1+max2+nums[mid])?max:(max1+max2+nums[mid]);
}