c语言用分治法求最大 子序数和

在 C 语言中，使用分治法求解数组的最大子序列和（Maximum Subarray Sum），通常可以借助 Kadane's Algorithm（凯撒算法）。这个算法是一种动态规划方法，步骤如下：

1. 定义两个变量 `max_current` 和 `max_global`，分别表示当前连续子数组的最大值和从开始到当前位置的最大值。
2. 遍历整个数组，对于每个元素 `arr[i]`：
a. 如果 `arr[i]` + `max_current` > `arr[i]`，说明加上当前元素后的子数组和更大，更新 `max_current = arr[i] + max_current`。
b. 否则，`max_current` 只能保持原样或等于 `arr[i]`，因为单独一个负数会使和变小。
c. 比较 `max_current` 和 `max_global`，如果 `max_current` 更大，就更新 `max_global`。
3. 最终 `max_global` 就是数组的最大子序列和。

下面是简单的 C 代码示例：

#include <stdio.h>
int maxSubArraySum(int arr[], int size) {
    if (size == 0) return 0; // 如果数组为空，则返回0
    int max_current = arr[0];
    int max_global = arr[0];

    for (int i = 1; i < size; i++) {
        max_current = (arr[i] > max_current + arr[i]) ? arr[i] : max_current + arr[i]; // 更新最大子数组和
        if (max_current > max_global)
            max_global = max_current; // 更新全局最大值
    }
    return max_global;
}

int main() {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = maxSubArraySum(arr, n);
    printf("最大子序列和是: %d\n", result);
    return 0;
}