c语言求最大子数组

### C语言实现最大子数组问题 #### 分治法解决方案 分治法通过将原问题分解成更小规模的相同问题来逐步解决问题。对于最大子数组问题而言，可以考虑三种情况的最大子数组位置： - 完全位于左半边 - 跨越中间部分 - 完全位于右半边 针对这三种情形分别计算并取其中最大的作为最终结果。 ```c #include <stdio.h> #include <limits.h> // 计算跨越中点的最大子数组和 int find_max_crossing_subarray(int *arr, int low, int mid, int high) { int sum = 0; int left_sum = INT_MIN; for (int i = mid; i >= low; --i) { sum += arr[i]; if (sum > left_sum) { left_sum = sum; } } sum = 0; int right_sum = INT_MIN; for (int j = mid + 1; j <= high; ++j) { sum += arr[j]; if (sum > right_sum) { right_sum = sum; } } return left_sum + right_sum; } // 主函数用于寻找最大子数组 int max_sub_array_divide_conquer(int *arr, int low, int high) { if (high == low) // 基本情况：只有一个元素 return arr[low]; int mid = (low + high) / 2; // 递归调用处理三个区域 int left_sum = max_sub_array_divide_conquer(arr, low, mid); int right_sum = max_sub_array_divide_conquer(arr, mid + 1, high); int cross_sum = find_max_crossing_subarray(arr, low, mid, high); // 返回这三个值中的最大者 if ((left_sum >= right_sum) && (left_sum >= cross_sum)) return left_sum; else if ((right_sum >= left_sum) && (right_sum >= cross_sum)) return right_sum; else return cross_sum; } ``` 此方法的时间复杂度为O(nlogn)，适用于较大规模的数据集[^1]。 #### 动态规划/贪心算法方案 另一种常见的做法是采用动态规划的思想，在遍历过程中维护两个变量`preSum`表示前缀累积和以及`MaxSum`记录到目前为止遇到过的最大子数组和。每当访问一个新的元素时更新这两个量，并据此调整最优解。 ```c int maxSubArray_greedy(int* nums, int numsSize){ int preSum = 0, MaxSum = -10000, curSum = nums[0]; for(int i = 0;i < numsSize;i++){ if(i==0) preSum = 0; else preSum += nums[i-1]; if(preSum<0){ curSum = nums[i]; preSum = 0; }else{ curSum = preSum + nums[i]; } if(curSum>MaxSum){ MaxSum = curSum; } } return MaxSum; } ``` 这种方法只需要一次线性扫描即可完成任务，时间复杂度降到了O(n)[^3]。