首页算法求数列的最大子段和C语言

算法求数列的最大子段和C语言

时间: 2025-01-05 10:38:09 浏览: 39

算法求解最大子段和的问题通常使用Kadane's Algorithm（康达拉赫算法），这是一个动态规划的经典例子。下面是用C语言实现的一个简单版本： ```c #include <stdio.h> // 定义函数求解最大子段和 int maxSubArray(int arr[], int size) { 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]); printf("最大的子数组和是 %d\n", maxSubArray(arr, n)); return 0; } ``` 在这个程序中，`max_sub_array` 函数遍历输入数组 `arr`，通过比较当前元素和加上当前元素后的子数组和，找到新的最大子数组和。如果当前元素加上原来的局部最大子数组和更大，则更新当前子数组和；如果加上当前元素后反而变小了，就直接舍弃。

阅读全文