、 最大子段和问题： 给定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语言分治算法分别实现） 源程序及运行结果：

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

#include <stdio.h>

// 分治算法求解最大子段和问题
int divideConquer(int a[], int left, int right) {
    if (left == right) {
        return a[left] > 0 ? a[left] : 0; // 当只有一个数时，返回该数或0
    }
    int mid = (left + right) / 2;
    int leftMax = divideConquer(a, left, mid); // 左半部分最大子段和
    int rightMax = divideConquer(a, mid+1, right); // 右半部分最大子段和

    // 计算跨中点的最大子段和
    int leftSum = 0, leftMaxSum = 0;
    for (int i = mid; i >= left; i--) {
        leftSum += a[i];
        if (leftSum > leftMaxSum) {
            leftMaxSum = leftSum;
        }
    }
    int rightSum = 0, rightMaxSum = 0;
    for (int i = mid+1; i <= right; i++) {
        rightSum += a[i];
        if (rightSum > rightMaxSum) {
            rightMaxSum = rightSum;
        }
    }
    int crossMax = leftMaxSum + rightMaxSum;

    // 返回三个值中的最大值
    int max = leftMax > rightMax ? leftMax : rightMax;
    return max > crossMax ? max : crossMax;
}

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

代码执行结果为：最大子段和为：20。