/*from : introduction to algorithm chapter fouralgorithm:divide and conquerthe 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));}