先說下思路：利用分治的思想，對一個(gè)數(shù)組進(jìn)行三種情況的劃分，1.[low,mid]葫隙、2.[mid,high]和3.跨界子數(shù)組[low,high]
最大子數(shù)組必然出現(xiàn)在這三種情況之一存璃。而第1、2種情況蜻势，又同樣適用于最大子數(shù)組的遞歸情況，也就是說求第1鹉胖、2種情況的遞歸思想和遞歸求一個(gè)數(shù)組的最大子數(shù)組的問題是一樣的握玛。
因此我們只要能實(shí)現(xiàn)求出最大跨界的子數(shù)組就找到了答案。

求跨界的最大子數(shù)組的思路就是：查看[i,mid]和[mid+1,i]的情況甫菠，分別求出這兩種情況的最大值和邊界挠铲，再對最大值求和，便找到了跨界最大子數(shù)組的和以及左右的邊界值寂诱。
以下是求跨界的最大子數(shù)組的C語言實(shí)現(xiàn)：

int *findMaxCrossingSubarray(int arr[], int low, int mid, int high)
{
    int *a = calloc(3, sizeof(int));
    int leftSum = INT_MIN;
    int leftMaxIndex = low;
    int sum = 0;
    for (int i = mid; i >= low; i--)
    {
        sum += arr[i];
        if (sum > leftSum)
        {
            leftSum = sum;
            leftMaxIndex = i;
        }
    }
    int rightSum = INT_MIN;
    int rightMaxIndex = high;
    sum = 0;
    for (int i = mid + 1; i <= high; i++)
    {

        sum += arr[i];
        if (sum > rightSum)
        {
            rightSum = sum;
            rightMaxIndex = i;
        }
    }
    a[0] = leftMaxIndex;
    a[1] = rightMaxIndex;
    a[2] = leftSum + rightSum;
    return a;
}

容易疏漏的地方：循環(huán)的時(shí)候拂苹，i的邊界條件。
以下代碼是完整的C語言遞歸實(shí)現(xiàn)：

//遞歸求解最大自數(shù)組的問題
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int *findMaxCrossingSubarray(int arr[], int low, int mid, int high); //尋找最大跨界子數(shù)組
int *findMaximumSubarray(int arr[], int low, int high);              //遞歸尋找最大子數(shù)組

int main()
{
    int arr[16] = {13, -3, -25, 1, -3, 16, 23, 18, -20, -7, -12, -50, -22, 15, -4, 7};
    int *result = findMaximumSubarray(arr, 0, 15);
    printf("左邊界為%d", result[0]);
    printf("右邊界為%d", result[1]);
    printf("最大跨界子數(shù)組的和為%d", result[2]);
    free(result);
    return 0;
}
//返回最大自數(shù)組的左右邊界和最大子數(shù)組的和
int *findMaxCrossingSubarray(int arr[], int low, int mid, int high)
{
    int *a = calloc(3, sizeof(int));
    int leftSum = INT_MIN;
    int leftMaxIndex = low;
    int sum = 0;
    for (int i = mid; i >= low; i--)
    {
        sum += arr[i];
        if (sum > leftSum)
        {
            leftSum = sum;
            leftMaxIndex = i;
        }
    }
    int rightSum = INT_MIN;
    int rightMaxIndex = high;
    sum = 0;
    for (int i = mid + 1; i <= high; i++)
    {

        sum += arr[i];
        if (sum > rightSum)
        {
            rightSum = sum;
            rightMaxIndex = i;
        }
    }
    a[0] = leftMaxIndex;
    a[1] = rightMaxIndex;
    a[2] = leftSum + rightSum;
    return a;
}

int *findMaximumSubarray(int arr[], int low, int high)
{
    int *a = calloc(3, sizeof(int));
    if (high == low)
    {
        a[0] = low;
        a[1] = high;
        a[2] = arr[low];
        return a;
    }
    int mid = (low + high) / 2;
    int *leftResult = findMaximumSubarray(arr, low, mid);
    int *rightResult = findMaximumSubarray(arr, mid + 1, high);
    int *midResult = findMaxCrossingSubarray(arr, low, mid, high);
    if (leftResult[2] >= midResult[2] && leftResult[2] >= rightResult[2])
    {
        free(rightResult);
        free(midResult);
        return leftResult;
    }
    else if (rightResult[2] >= midResult[2] && rightResult[2] >= leftResult[2])
    {
        free(leftResult);
        free(midResult);
        return rightResult;
    }
    else
    {
        free(leftResult);
        free(rightResult);
        return midResult;
    }
}

復(fù)雜度為O(nlgn)痰洒，完畢瓢棒。