最大子段和-分治法应用的C语言代码和运行结果图
时间: 2024-10-08 16:23:17 浏览: 33
最大子段和问题通常通过Kadane's Algorithm(分治法的一种变体)来解决,这个算法主要是动态规划的应用。以下是C语言的一个简单实现:
```c
#include <stdio.h>
int maxSubArray(int arr[], int size) {
if (size <= 1)
return arr[0];
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];
max_global = (max_global > max_current) ? 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("The maximum sum of a subarray is: %d\n", maxSubArray(arr, n));
return 0;
}
```
运行此代码后,它将计算给定数组`arr`中连续元素的最大和,并打印出来。例如,如果输入数组是`{-2, -3, 4, -1, -2, 1, 5, -3}`,则输出将是`7`,因为最大的连续子数组是`{4, -1, -2, 1, 5}`,它们的和为`7`。
由于这是一个文本交互环境,无法显示图形结果。但是你可以自行在本地运行这段代码,观察控制台的输出。
阅读全文