怎么求一个数组的最大子数组
时间: 2024-10-10 19:04:25 浏览: 1
求一个数组的最大子数组(Maximum Subarray)通常是指在一个整数数组中找到一个连续子数组,使得这个子数组的所有元素之和最大。这个问题可以使用著名的Kadane算法来解决,这是一个线性时间复杂度O(n)的算法,步骤如下:
1. 初始化两个变量:`max_current`和`max_global`,分别代表当前子数组的最大和以及全局最大和,初始值都设为数组的第一个元素。
2. 遍历数组,对于每个元素`num`:
- 更新`current_sum`,如果`current_sum + num`大于`num`本身,则说明加上当前元素后和更大;否则,将`current_sum`置为`num`,因为负数加负数会使和变小。
- 如果`current_sum`比`max_global`大,就更新`max_global`。
3. 最后`max_global`即为所求的最大子数组和。
下面是一个简单的C语言实现示例:
```c
#include <stdio.h>
int maxSubArray(int arr[], int n) {
int max_current = arr[0];
int max_global = arr[0];
for (int i = 1; i < n; ++i) {
int current_sum = max(arr[i], current_sum + arr[i]);
if (current_sum > max_global)
max_global = current_sum;
}
return max_global;
}
int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Max sum of a contiguous subarray is %d\n", maxSubArray(arr, size));
return 0;
}
```