最大子序和分治解法C语言

最大子序和的分治算法，也称为Kadane's Algorithm，是一种经典的动态规划问题，用于找出给定整数数组中的连续子序列的最大和。以下是C语言的一个简单实现：

#include <stdio.h>

int maxSubArray(int arr[], int size) {
    if (size == 1) {
        return arr[0]; // 基本情况，只有一个元素，其本身即为最大子序和
    }

    int maxSoFar = arr[0], maxEndingHere = arr[0];
    for (int i = 1; i < size; i++) {
        maxEndingHere = (arr[i] > maxEndingHere + arr[i]) ? arr[i] : maxEndingHere + arr[i];
        maxSoFar = (maxSoFar > maxEndingHere) ? maxSoFar : maxEndingHere;
    }
    return maxSoFar;
}

int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("The maximum contiguous sum is %d\n", maxSubArray(arr, n));
    return 0;
}

这个算法的工作原理是，对于每个位置i，计算以i结尾的最大子数组和maxEndingHere。如果当前位置的值加上当前maxEndingHere大于当前位置的值，则更新maxEndingHere；否则，从当前位置开始重新计算子数组和。同时，它还维护着整个已遍历部分的最大子数组和maxSoFar。