kadane c语言
时间: 2024-09-15 19:12:26 浏览: 29
Kadane's algorithm,也称为最大子数组和算法,是一种用于寻找给定数组中连续子数组的最大和的动态规划方法。它是由印度计算机科学家Jay Kadane在1980年提出的。在C语言中,这个算法可以这样实现:
```c
#include <stdio.h>
#include <limits.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, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(arr)/sizeof(arr[0]);
printf("最大子数组和: %d\n", maxSubArray(arr, n));
return 0;
}
```
在这个代码片段中,`maxSubArray`函数遍历输入数组,计算每个元素开始到当前位置的最大子数组和,并记录全局最大和。如果当前元素加上前一个元素的和更大,则更新当前最大和;否则,从当前元素开始重建新的子数组。