C语言用分治法求最大连续子序列和

C语言可以利用分治策略解决最大连续子序列和的问题，通常通过Kadane's Algorithm（卡尔曼算法）实现。这个算法的基本思想是动态地维护两个变量：当前元素的和`currentSum`和全局最大子序列和`maxSoFar`。

以下是简单的步骤：

1. 定义两个变量：`currentSum`初始化为第一个元素，`maxSoFar`初始化为负无穷大。
2. 遍历数组`arr`中的每个元素：
a. 如果`currentSum`加上当前元素大于0，则将当前元素加到`currentSum`上；
b. 否则，说明当前元素是负数，应从`currentSum`开始清零，并更新`currentSum`为当前元素。
c. 每次更新`currentSum`的同时，如果它比`maxSoFar`大，就更新`maxSoFar`。
3. 最终，`maxSoFar`就是最大的连续子序列和。

#include <stdio.h>
int maxSubArray(int arr[], int size) {
    if (size == 1) return arr[0];
    int maxCurrent = arr[0];
    int maxGlobal = arr[0];

    for (int i=1; i<size; i++) {
        maxCurrent = (arr[i] > maxCurrent + arr[i]) ? arr[i] : maxCurrent + arr[i];
        maxGlobal = max(maxGlobal, maxCurrent);
    }
    return maxGlobal;
}

// 测试函数
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Max subarray sum is %d\n", maxSubArray(arr, n));
    return 0;
}