分别用暴力法、分而治之法、动态规划法求解最大子段和问题，使用c语言

暴力法：

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

int max_sub_array(int* nums, int nums_size) {
    int max_sum = nums[0];
    for (int i = 0; i < nums_size; i++) {
        int cur_sum = nums[i];
        for (int j = i + 1; j < nums_size; j++) {
            cur_sum += nums[j];
            if (cur_sum > max_sum) {
                max_sum = cur_sum;
            }
        }
    }
    return max_sum;
}

int main() {
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int nums_size = sizeof(nums) / sizeof(int);
    int max_sum = max_sub_array(nums, nums_size);
    printf("The maximum subarray sum is: %d\n", max_sum);
    return 0;
}

分而治之法：

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

int max_sub_array(int* nums, int start, int end) {
    if (start == end) {
        return nums[start];
    }
    int mid = start + (end - start) / 2;
    int left_max = max_sub_array(nums, start, mid);
    int right_max = max_sub_array(nums, mid + 1, end);

    int left_sum = nums[mid];
    int max_left_sum = left_sum;
    for (int i = mid - 1; i >= start; i--) {
        left_sum += nums[i];
        if (left_sum > max_left_sum) {
            max_left_sum = left_sum;
        }
    }

    int right_sum = nums[mid + 1];
    int max_right_sum = right_sum;
    for (int i = mid + 2; i <= end; i++) {
        right_sum += nums[i];
        if (right_sum > max_right_sum) {
            max_right_sum = right_sum;
        }
    }

    int cross_max = max_left_sum + max_right_sum;
    int max_sum = left_max > right_max ? left_max : right_max;
    max_sum = max_sum > cross_max ? max_sum : cross_max;
    return max_sum;
}

int main() {
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int nums_size = sizeof(nums) / sizeof(int);
    int max_sum = max_sub_array(nums, 0, nums_size - 1);
    printf("The maximum subarray sum is: %d\n", max_sum);
    return 0;
}

动态规划法：

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

int max_sub_array(int* nums, int nums_size) {
    int max_sum = nums[0];
    int cur_sum = nums[0];
    for (int i = 1; i < nums_size; i++) {
        cur_sum = nums[i] > cur_sum + nums[i] ? nums[i] : cur_sum + nums[i];
        max_sum = max_sum > cur_sum ? max_sum : cur_sum;
    }
    return max_sum;
}

int main() {
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int nums_size = sizeof(nums) / sizeof(int);
    int max_sum = max_sub_array(nums, nums_size);
    printf("The maximum subarray sum is: %d\n", max_sum);
    return 0;
}

注意：以上三个代码段均未进行错误处理和边界检查，仅供参考。