找到一个最大的一笔连续的子阵 [英] Finding a maximum sum contiguous sub array
问题描述
我写一个code，找到最大和连续子阵列C中的逻辑据我似乎不错，但还是输出是不正确的。请看code。该算法将一更大的阵列分为2子阵列。然后，它通过检查左阵列，右阵列和还含有中点的阵列，用于最大和子阵列检查（它会检查右侧和从左侧中点，然后返回的最大总和子阵列包含中点）。
为int * cross_max（INT改编[]，INT低，诠释中期，诠释高）
{
INT left_max，left_sum = -2000;
INT总和= 0;
INT I;
对于（i =中间; I＆GT; =低;我 - ）
{
总和=总和+改编[I]
如果（总和＆GT; left_sum）
{
left_sum =总和;
left_max =我;
}
}
INT right_max，right_sum = -2000;
对于（I =中等+ 1; I＆LT; =高;我++）
{
总和=总和+改编[I]
如果（总和＆GT; right_sum）
{
right_sum =总和;
right_max =我;
}
}
// 0 - 总和
//指数 - 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个最大金额=％d个\ N，* P）;
的printf（\ n低=％D \ N，*（P + 1））;
的printf（\ n个高速=％D \ N，*（P + 2））;
返回磷;
}
INT * find_max（INT改编[]，INT低，诠释高）
{
INT temp_arr [3] = {0,0,0};
如果（低==高）
{
temp_arr [0] = ARR [小]
temp_arr [1] =低;
temp_arr [2] =低;
INT * Q = temp_arr;
返回q;
}
INT中期=（低+高）/ 2;
INT * A1 = find_max（ARR，低，中）;
INT * A2 = find_max（ARR，中+ 1，高）;
INT * A3 = cross_max（ARR，低，中，高）;
如果（* A1＆GT; * A2＆功放;＆放大器; * A1＆GT; * A3）
返回A1;
否则，如果（* A2＆GT; * A1和放大器;＆放大器; * A2＆GT; * A3）
返回A2;
其他
返回A3;
}
诠释的main（）
{
INT改编[8] = {1,1,2，-2,3,3,4，-4};
INT *点= find_max（ARR，0,7）;
的printf（\ N个最大金额=％d个\ N，*点）;
的printf（\ n低=％D \ N，*（点+ 1））;
的printf（\ n个高速=％D \ N，*（点+ 2））;
返回0;
}
有几个与不确定的行为问题，在code：
首先，你通过 9 为高将被用于索引八十元k-元数组。这将是第十届，因为 cross_max 你循环而 I＆LT; =高，所以你将指数改编[9] 。记住数组的索引是从零到大小减一（这样你就可以索引从 0 到 7 您的阵列）。该指数超出范围将包含不确定的（即随机）值。
第二个问题是，你从 cross_max 返回指向一个局部变量。这将导致不确定的行为，当您使用返回的指针。局部变量仅他们中声明的范围内才有效，而当该函数返回所使用的局部变量的存储区域将被回收并用于下一功能
I am writing a code to find the maximum sum contiguous sub array in C. The logic seems fine according to me, but still the output is not correct. Please look into the code. The algorithm divides a bigger array into 2 sub-arrays. It then checks for maximum sum sub-array by examining the left array , right array and also the array containing the midpoint (It will check right and left from the midpoint and then return the maximum sum sub-array containing the midpoint).
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<=high;i++)
{
sum = sum + arr[i];
if(sum > 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;
}
There are a couple of problems with undefined behavior in your code:
The first is that you pass 9 as high which will be used to index the tenth element of an eight-element array. It will be the tenth because in cross_max you loop while i <= high, so you will index arr[9]. Remember that array indexes are from zero to the size minus one (so you can index from 0 to 7 for your array). The indexes out of bounds will contain undefined (i.e. random) values.
The second problem is that you are returning pointers to a local variable from cross_max. This will lead to undefined behavior when you use that returned pointer. Local variables are only valid inside the scope they were declared, and when the function returns the memory area used by the local variables will be reclaimed and used for the next function.
这篇关于找到一个最大的一笔连续的子阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
