divide-conquer-combine(4.1 from the introduction to algorithm)

/*
from : introduction to algorithm chapter four
algorithm:divide and conquer
the time complexity of this algorithm is O(n * logn)

*/
#include <stdio.h>

int Find_max_crossing_subarray(int *a, int low, int mid, int high)
{
    int left_sum = -0xffff;
    int sum = 0;
    for (int i = mid; i >= low; i--)
    {
        sum += a[i];
        if (sum > left_sum)
            left_sum = sum;
    }
    int right_sum = -0xffff;
    sum = 0;
    for (int j = mid+1; j <= high; j++)
    {
        sum += a[j];
        if (sum > right_sum)
            right_sum = sum;
    }
    return left_sum + right_sum;
}

int find_maximum_subarray(int *a, int low, int high)
{
    if (high == low)
    {
        return *(a+high); // base case: only one element
    }
    else
    {
        int mid = (high + low)/2;
        if ((find_maximum_subarray(a, low, mid) >= find_maximum_subarray(a, mid+1, high))&&(find_maximum_subarray(a, low, mid)>=Find_max_crossing_subarray(a,low,mid,high)))
        {
            return find_maximum_subarray(a, low, mid);
        }
        else if ((find_maximum_subarray(a, mid+1, high) >= find_maximum_subarray(a, low, mid))&&(find_maximum_subarray(a, mid+1, high) >= Find_max_crossing_subarray(a,low,mid,high)))
        {
            return find_maximum_subarray(a, mid+1, high);
        }
        else
        {
            return Find_max_crossing_subarray(a, low, mid, high);
        }
    }
}

int main()
{
    int a[16]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
    int b[6]={1,2,3,4,5};
    printf("%d\n",find_maximum_subarray(a,0,15));
    printf("%d\n",find_maximum_subarray(b,0,5));
}