最大子段和问题： 给定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>
#include <limits.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int max_cross_sum(int arr[], int start, int mid, int end) {
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= start; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }

    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= end; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }

    return left_sum + right_sum;
}

int max_subarray_sum(int arr[], int start, int end) {
    if (start == end) {
        return arr[start];
    } else {
        int mid = (start + end) / 2;
        int left_sum = max_subarray_sum(arr, start, mid);
        int right_sum = max_subarray_sum(arr, mid + 1, end);
        int cross_sum = max_cross_sum(arr, start, mid, end);
        return max(max(left_sum, right_sum), cross_sum);
    }
}

int main() {
    int arr[] = {-20, 11, -4, 13, -5, -2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_sum = max_subarray_sum(arr, 0, n - 1);
    printf("Max subarray sum: %d\n", max_sum);
    return 0;
}

运行结果如下：

Max subarray sum: 20

这个程序的基本思路是使用分治算法，将数组分为两部分，分别求出左半部分、右半部分和跨越中点的子段和的最大值，然后再在这三个最大值中取较大的那个作为整个数组的最大子段和。通过这样的递归过程，最后就能得到整个数组的最大子段和。