最大子段和问题: 给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0,依此定义,所求的最优值为: Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如,当(a[1],a[2],a[3],a[4],a[5],a[6])=(-20,11,-4,13,-5,-2)时,最大子段和为20(11,-4,13)。(用c语言使用分治算法分别实现) 源程序及运行结果:
时间: 2023-12-02 09:02:52 浏览: 61
下面是用分治算法实现最大子段和问题的 C 语言程序:
```c
#include <stdio.h>
#include <limits.h>
int max(int a, int b) {
return a > b ? a : b;
}
int max_cross_sum(int arr[], int start, int mid, int end) {
int sum = 0;
int left_sum = INT_MIN;
for (int i = mid; i >= start; i--) {
sum += arr[i];
if (sum > left_sum) {
left_sum = sum;
}
}
sum = 0;
int right_sum = INT_MIN;
for (int i = mid + 1; i <= end; i++) {
sum += arr[i];
if (sum > right_sum) {
right_sum = sum;
}
}
return left_sum + right_sum;
}
int max_subarray_sum(int arr[], int start, int end) {
if (start == end) {
return arr[start];
} else {
int mid = (start + end) / 2;
int left_sum = max_subarray_sum(arr, start, mid);
int right_sum = max_subarray_sum(arr, mid + 1, end);
int cross_sum = max_cross_sum(arr, start, mid, end);
return max(max(left_sum, right_sum), cross_sum);
}
}
int main() {
int arr[] = {-20, 11, -4, 13, -5, -2};
int n = sizeof(arr) / sizeof(arr[0]);
int max_sum = max_subarray_sum(arr, 0, n - 1);
printf("Max subarray sum: %d\n", max_sum);
return 0;
}
```
运行结果如下:
```
Max subarray sum: 20
```
这个程序的基本思路是使用分治算法,将数组分为两部分,分别求出左半部分、右半部分和跨越中点的子段和的最大值,然后再在这三个最大值中取较大的那个作为整个数组的最大子段和。通过这样的递归过程,最后就能得到整个数组的最大子段和。
阅读全文