LeetCode:Maximum Subarray

LeetCode:Maximum Subarray

題目描述：

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [?2,1,?3,4,?1,2,1,?5,4],
the contiguous subarray [4,?1,2,1] has the largest sum = 6.

代碼：

int Solution::maxSubArray(int A[], int n)
{
   return calculateMax(A,0,n-1);
}

int Solution::calculateMax(int A[],int left,int right)
{
    if(left == right)
        return A[left];
    int mid = (left + right) / 2;
    int subleft_max = calculateMax(A,left,mid);
    int subright_max = calculateMax(A,mid+1,right);
    int sum = A[mid];
    int left_max = A[mid];
    int i;
    for(i = mid-1;i >= left;i--)
    {
        sum = sum + A[i];
        if(sum > left_max)
            left_max = sum;
    }
    sum = A[mid+1];
    int right_max = A[mid+1];
    for(i = mid+2;i <= right;i++)
    {
        sum = sum + A[i];
        if(sum > right_max)
            right_max = sum;
    }
    int temp;
    if(subleft_max > subright_max)
        temp = subleft_max;
    else
        temp = subright_max;
    if(temp > (left_max + right_max))
        return temp;
    else
        return left_max + right_max;
}