用分而治之解决最大子数组问题
时间: 2023-09-06 09:11:49 浏览: 75
最大子数组问题也可以使用分治法来解决。具体地,将原始数组分成左右两个子数组,递归地求出左右子数组的最大子数组,然后再求跨越左右子数组的最大子数组。跨越左右子数组的最大子数组可以通过计算以中心点为起点的向左最大子数组和以中心点为终点的向右最大子数组的和来得到。最后比较三个结果中的最大值即可。该算法的时间复杂度为 O(nlogn)。
相关问题
最大字段和问题分而治之算法c
最大字段和问题可以使用分治算法来解决,具体步骤如下:
1. 将数组分成两部分,分别求出左半部分的最大字段和、右半部分的最大字段和以及跨越中点的最大字段和。
2. 左半部分和右半部分的最大字段和可以使用递归来计算,跨越中点的最大字段和可以使用线性算法来计算。
3. 最终的最大字段和为上述三者中的最大值。
C语言代码实现:
```
#include <stdio.h>
#include <limits.h>
int max(int a, int b) {
return a > b ? a : b;
}
int max_crossing_sum(int arr[], int l, int m, int h) {
int sum = 0;
int left_sum = INT_MIN;
for (int i = m; i >= l; i--) {
sum += arr[i];
if (sum > left_sum)
left_sum = sum;
}
sum = 0;
int right_sum = INT_MIN;
for (int i = m + 1; i <= h; i++) {
sum += arr[i];
if (sum > right_sum)
right_sum = sum;
}
return left_sum + right_sum;
}
int max_subarray_sum(int arr[], int l, int h) {
if (l == h)
return arr[l];
int m = (l + h) / 2;
return max(max(max_subarray_sum(arr, l, m),
max_subarray_sum(arr, m + 1, h)),
max_crossing_sum(arr, l, m, h));
}
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(arr) / sizeof(arr[0]);
int max_sum = max_subarray_sum(arr, 0, n - 1);
printf("Maximum contiguous sum is %d\n", max_sum);
return 0;
}
```
分别用暴力法、分而治之法、动态规划法求解最大子段和问题,使用c语言
暴力法:
```c
#include <stdio.h>
#include <stdlib.h>
int max_sub_array(int* nums, int nums_size) {
int max_sum = nums[0];
for (int i = 0; i < nums_size; i++) {
int cur_sum = nums[i];
for (int j = i + 1; j < nums_size; j++) {
cur_sum += nums[j];
if (cur_sum > max_sum) {
max_sum = cur_sum;
}
}
}
return max_sum;
}
int main() {
int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int nums_size = sizeof(nums) / sizeof(int);
int max_sum = max_sub_array(nums, nums_size);
printf("The maximum subarray sum is: %d\n", max_sum);
return 0;
}
```
分而治之法:
```c
#include <stdio.h>
#include <stdlib.h>
int max_sub_array(int* nums, int start, int end) {
if (start == end) {
return nums[start];
}
int mid = start + (end - start) / 2;
int left_max = max_sub_array(nums, start, mid);
int right_max = max_sub_array(nums, mid + 1, end);
int left_sum = nums[mid];
int max_left_sum = left_sum;
for (int i = mid - 1; i >= start; i--) {
left_sum += nums[i];
if (left_sum > max_left_sum) {
max_left_sum = left_sum;
}
}
int right_sum = nums[mid + 1];
int max_right_sum = right_sum;
for (int i = mid + 2; i <= end; i++) {
right_sum += nums[i];
if (right_sum > max_right_sum) {
max_right_sum = right_sum;
}
}
int cross_max = max_left_sum + max_right_sum;
int max_sum = left_max > right_max ? left_max : right_max;
max_sum = max_sum > cross_max ? max_sum : cross_max;
return max_sum;
}
int main() {
int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int nums_size = sizeof(nums) / sizeof(int);
int max_sum = max_sub_array(nums, 0, nums_size - 1);
printf("The maximum subarray sum is: %d\n", max_sum);
return 0;
}
```
动态规划法:
```c
#include <stdio.h>
#include <stdlib.h>
int max_sub_array(int* nums, int nums_size) {
int max_sum = nums[0];
int cur_sum = nums[0];
for (int i = 1; i < nums_size; i++) {
cur_sum = nums[i] > cur_sum + nums[i] ? nums[i] : cur_sum + nums[i];
max_sum = max_sum > cur_sum ? max_sum : cur_sum;
}
return max_sum;
}
int main() {
int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int nums_size = sizeof(nums) / sizeof(int);
int max_sum = max_sub_array(nums, nums_size);
printf("The maximum subarray sum is: %d\n", max_sum);
return 0;
}
```
注意:以上三个代码段均未进行错误处理和边界检查,仅供参考。