求最大字段和（穷举法、动态规划、分治法）c语言代码实现

求最大字段和通常涉及到数组或矩阵的遍历问题，可以使用多种算法策略来解决，如穷举法、动态规划和分治法。这里分别给出三种方法的基本C语言代码实现：

1. **穷举法** (Brute Force):

#include <stdio.h>

int maxSubarray(int arr[], int n) {
    int max_current = arr[0];
    int max_global = arr[0];

    for (int i = 1; i < n; i++) {
        max_current = (arr[i] > max_current + arr[i]) ? arr[i] : max_current + arr[i];
        max_global = (max_current > max_global) ? max_current : max_global;
    }
    return max_global;
}

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;
}

2. **动态规划** (Dynamic Programming):

#include <stdio.h>
#include <stdlib.h>

int maxSubarraySum(int arr[], int n) {
    int max_so_far = arr[0];
    int curr_max = arr[0];

    for (int i = 1; i < n; i++) {
        curr_max = (arr[i] > curr_max + arr[i]) ? arr[i] : curr_max + arr[i];
        max_so_far = (curr_max > max_so_far) ? curr_max : max_so_far;
    }
    return max_so_far;
}

int main() {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Max subarray sum using dynamic programming is %d\n", maxSubarraySum(arr, n));
    return 0;
}

3. **分治法** (Divide and Conquer, 一般此场景不适合分治，因为它不是一个问题的自然分解，但为了展示，我们可以想象用类似分治的方式来寻找最大连续子数组):

// 这里分治法实现并不典型，因为该问题不适用于分治策略，但它可以展示递归思想
#include <stdio.h>

void maxSubarrayRec(int arr[], int start, int end, int* maxSoFar) {
    if (start == end) {
        *maxSoFar = MAX(*maxSoFar, arr[start]);
    } else {
        int mid = (start + end) / 2;
        int leftMax = *maxSoFar;
        int rightMax = *maxSoFar;

        maxSubarrayRec(arr, start, mid, &leftMax);
        maxSubarrayRec(arr, mid + 1, end, &rightMax);

        // 更新全局最大值
        *maxSoFar = MAX(leftMax, rightMax + arr[mid]);
    }
}

int main() {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxSoFar = INT_MIN;
    maxSubarrayRec(arr, 0, n - 1, &maxSoFar);
    printf("Max subarray sum using a non-standard divide-and-conquer approach is %d\n", maxSoFar);
    return 0;
}

请注意，分治法在这道题上并不是最有效的解决方案。