使用c语言：给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-20,11,-4,13,-5,-2)时，最大子段和为20（11,-4,13）。（使用分治算法分别实现）

以下是使用分治算法实现求解最大子段和的C语言代码：

#include <stdio.h>

#define INF -2147483647

// 求解跨越中点的最大子段和
int maxCrossingSum(int arr[], int left, int mid, int right) {
    int leftSum = INF, rightSum = INF, sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > leftSum) {
            leftSum = sum;
        }
    }
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > rightSum) {
            rightSum = sum;
        }
    }
    return leftSum + rightSum;
}

// 分治求解最大子段和
int maxSubarraySum(int arr[], int left, int right) {
    if (left == right) {
        return arr[left] > 0 ? arr[left] : 0;
    }
    int mid = (left + right) / 2;
    int leftMaxSum = maxSubarraySum(arr, left, mid);
    int rightMaxSum = maxSubarraySum(arr, mid + 1, right);
    int crossMaxSum = maxCrossingSum(arr, left, mid, right);
    int maxSum = leftMaxSum > rightMaxSum ? leftMaxSum : rightMaxSum;
    maxSum = maxSum > crossMaxSum ? maxSum : crossMaxSum;
    return maxSum;
}

int main() {
    int arr[] = {-20, 11, -4, 13, -5, -2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxSum = maxSubarraySum(arr, 0, n - 1);
    printf("最大子段和为 %d\n", maxSum);
    return 0;
}

运行结果为：

最大子段和为 20

该算法的时间复杂度为O(nlogn)，比暴力算法的O(n^2)更优。