查找最大和的连续子数组

我正在编写一个代码来查找C中的最大和连续子数组。根据我的说法,逻辑似乎很好,但输出仍然不正确。 请查看代码。 该算法将较大的arrays分成2个子arrays。 然后通过检查左数组,右数组以及包含中点的数组来检查最大和子数组(它将检查中点的左右两边,然后返回包含中点的最大和子数组)。

int* cross_max(int arr[], int low, int mid, int high) { int left_max, left_sum = -2000; int sum = 0; int i; for(i=mid; i>=low;i--) { sum = sum + arr[i]; if(sum > left_sum) { left_sum = sum; left_max = i; } } int right_max, right_sum = -2000; for(i=mid+1; i right_sum) { right_sum = sum; right_max = i; } } // 0 - sum // indices - 1,2 int temp_arr[3] = {0,0,0}; temp_arr[0] = left_sum + right_sum; temp_arr[1] = left_max; temp_arr[2] = right_max; int *p = temp_arr; printf("\n Maximum sum = %d\n",*p); printf("\n low = %d\n",*(p+1)); printf("\n high = %d\n",*(p+2)); return p; } int* find_max(int arr[], int low, int high) { int temp_arr[3] = {0,0,0}; if(low == high) { temp_arr[0] = arr[low]; temp_arr[1] = low; temp_arr[2] = low; int *q = temp_arr; return q; } int mid = (low + high)/2; int* a1 = find_max(arr,low,mid); int* a2 = find_max(arr,mid+1,high); int* a3 = cross_max(arr,low,mid,high); if (*a1 > *a2 && *a1 > *a3) return a1; else if (*a2 > *a1 && *a2 > *a3) return a2; else return a3; } int main() { int arr[8] = {1,1,2,-2,3,3,4,-4}; int *point = find_max(arr,0,7); printf("\n Maximum sum = %d\n",*point); printf("\n low = %d\n",*(point+1)); printf("\n high = %d\n",*(point+2)); return 0; } 

您的代码中存在一些未定义行为的问题:

第一个是你将9传递给high ,这将用于索引八元素数组的第十个元素。 这将是第十个因为在cross_max你循环而i <= high ,所以你将索引arr[9] 。 请记住,数组索引从零到大小减一(因此您可以为数组索引从07 )。 超出范围的索引将包含未定义(即随机)值。

第二个问题是您从cross_max返回指向局部变量的cross_max 。 当您使用返回的指针时,这将导致未定义的行为。 局部变量仅在声明它们的范围内有效,并且当函数返回时,局部变量使用的内存区域将被回收并用于下一个函数。

稍微偏离主题,但这个问题以解决它的最佳方式而闻名(在线性时间内)。 您可以从规范中完全导出代码。

首先,正式定义问题:

给定 :整数数组A[0, N)

要求

 max(0 <= p <= q <= N : sum(p, q)) where sum(p, q) = sum(p <= i < q : A[i]) 

方法

X(n) = max(0 <= p <= q <= n : sum(p, q)) ,然后我们需要找到X(N) 。 我们通过归纳做到这一点:

 X(0) = max(0 <= p <= q <= 0 : sum(p, q)) = sum(0, 0) = sum(0 <= i < 0 : A[i]) = 0 

 X(n+1) = max(0 <= p <= q <= n+1 : sum(p, q)) = max(max(0 <= p <= q <= n : sum(p, q)), max(0 <= p <= n+1 : sum(p, n+1))) = max(X(n), Y(n+1)) 

其中Y(n) = max(0 <= p <= n : sum(p, n)) 。 我们现在还通过归纳确定Y(n)

 Y(0) = max(0 <= p <= 0 : sum(p, 0)) = sum(0, 0) = 0 

 Y(n+1) = max(0 <= p <= n+1 : sum(p, n+1)) = max(max(0 <= p <= n : sum(p, n+1)), sum(n+1, n+1))) = max(max(0 <= p <= n : sum(p, n)) + A[n], 0) = max(Y(n) + A[n], 0) 

代码

使用上面的分析,代码是微不足道的。

 int arr[8] = {1,1,2,-2,3,3,4,-4}; int N = 8; int x = 0; int y = 0; for (int n = 0; n < N; n++) { y = max(y + arr[n], 0); x = max(x, y); } printf("Maximum sum = %d\n", x); 

 int max(int a, int b) { if (a > b) return a; else return b; } 

该算法效率不高。 时间复杂度为o(n^2) 。 这是一个动态编程算法,它是o(n)

 /************************************************************************* > File Name: subarray.cpp > Author: luliang > Mail: lulyon@126.com > Created Time: 2013/09/10 Tuesday 15:49:23 ************************************************************************/ #include  typedef struct { int low; int high; int sum; }DPInfoType; int main() { int arr[8] = {1,1,2,-2,3,3,4,-4}; const int n = sizeof(arr) / sizeof(arr[0]); DPInfoType dp[n]; dp[0].low = 0; dp[0].high = 0; dp[0].sum = arr[0]; for(int i = 1; i < n; ++i) { if(dp[i - 1].sum > 0) { dp[i].low = dp[i - 1].low; dp[i].high = i; dp[i].sum = dp[i - 1].sum + arr[i]; } else { dp[i].low = i; dp[i].high = i; dp[i].sum = arr[i]; } } int max_index = 0; for(int i = 1; i < n; ++i) { if(dp[max_index].sum < dp[i].sum) max_index = i; } printf("\n Maximum sum = %d\n", dp[max_index].sum); printf("\n low = %d\n", dp[max_index].low); printf("\n high = %d\n", dp[max_index].high); return 0; } 

如前所述,在您的代码中使用指针是不合适的。 这段代码对我有用。

 #include  #define INF 1000000 int max (int a, int b) { if (a < b) return b; return a; } int findMaxCrossingSubarray (int arr[], int low, int mid, int high, int *start, int *end) { int i, left, right; int max_left, max_right; int left_sum = -INF; int sum = 0; for (i = mid; i >= 0; i--) { sum += arr[i]; if (sum > left_sum) { left_sum = sum; max_left = i; } } int right_sum = -INF; sum = 0; for (i = mid + 1; i <= high; i++) { sum += arr[i]; if (sum > right_sum) { right_sum = sum; max_right = i; } } *start = max_left; *end = max_right; return left_sum + right_sum; } int findMaxSubarray (int arr[], int low, int high, int *start, int *end) { if (low == high) return arr[low]; int mid = (high - low)/2 + low; int start1, start2, start3; int end1, end2, end3; // initialization of start and end for terminal cases. start1 = start3 = low; start2 = mid + 1; end1 = mid; end2 = end3 = high; int sum1 = findMaxSubarray(arr, low, mid, &start1, &end1); int sum2 = findMaxSubarray(arr, mid + 1, high, &start2, &end2); int sum3 = findMaxCrossingSubarray(arr, low, mid, high, &start3, &end3); int res = max(max(sum1, sum2), sum3); if (res == sum1) { *start = start1; *end = end1; } if (res == sum2) { *start = start2; *end = end2; } if (res == sum3) { *start = start3; *end = end3; } return res; } int main(int argc, char const *argv[]) { int size, i, item, result; printf("Enter the size of array: "); scanf("%d",&size); int arr[size]; printf("Enter the array:\n"); for (i = 0; i < size; ++i) { scanf("%d",&item); arr[i] = item; } int start = 0, end = size-1; result = findMaxSubarray(arr, 0, size-1, &start, &end); printf("Result: %d, start: %d and end: %d.\n", result, start, end); return 0; }