已知A=(2,-7,3,1,2,-3,5,-4,6,2),请使用c语言以分治算法求最大连续子数组
时间: 2023-10-09 16:10:54 浏览: 53
以下是使用分治算法求最大连续子数组的C语言代码:
#include <stdio.h>
struct Result {
int start;
int end;
int sum;
};
// 定义比较函数
int max(int a, int b) {
return a > b ? a : b;
}
int maxCrossingSubArray(int A[], int low, int mid, int high, struct Result* result) {
int leftSum = A[mid];
int sum = A[mid];
int i;
for (i = mid - 1; i >= low; i--) {
sum += A[i];
if (sum > leftSum) {
leftSum = sum;
result->start = i;
}
}
int rightSum = A[mid + 1];
sum = A[mid + 1];
int j;
for (j = mid + 2; j <= high; j++) {
sum += A[j];
if (sum > rightSum) {
rightSum = sum;
result->end = j;
}
}
result->sum = leftSum + rightSum;
return result->sum;
}
int maxSubArray(int A[], int low, int high, struct Result* result) {
if (low == high) {
result->start = low;
result->end = high;
result->sum = A[low];
return result->sum;
}
int mid = (low + high) / 2;
struct Result leftResult;
struct Result rightResult;
struct Result crossResult;
int leftSum = maxSubArray(A, low, mid, &leftResult);
int rightSum = maxSubArray(A, mid + 1, high, &rightResult);
int crossSum = maxCrossingSubArray(A, low, mid, high, &crossResult);
if (leftSum >= rightSum && leftSum >= crossSum) {
*result = leftResult;
return leftSum;
} else if (rightSum >= leftSum && rightSum >= crossSum) {
*result = rightResult;
return rightSum;
} else {
*result = crossResult;
return crossSum;
}
}
int main() {
int A[] = {2, -7, 3, 1, 2, -3, 5, -4, 6, 2};
int n = sizeof(A) / sizeof(int);
struct Result result;
int maxSum = maxSubArray(A, 0, n - 1, &result);
printf("最大连续子数组:\n");
int i;
for (i = result.start; i <= result.end; i++) {
printf("%d ", A[i]);
}
printf("\n");
printf("最大子数组和:%d\n", maxSum);
return 0;
}
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)