我正在尝试使用C语言中的除法和征服算法来解决最大子数组问题,我已经找到了在线解决方案,但是当我在IDE中运行时,它不会将&start和&end作为开始索引和结束索引的参数。我试过运行执行相同操作的其他代码,但仍然无法正常工作。已经在线运行过该软件的人提供了带有屏幕截图的解决方案,但最终无法使用。得到这些错误。
test.c:7:65:错误:在'&'标记之前的预期';',','或')'int maxcross_subarray(int * arr,int low,int mid,int high,int&start,int&end )
test.c:63:55:错误:在'&'令牌之前的预期';',','或')'int maximum_subarray(int * arr,int low,int high,int&start,int&end)
test.c:在函数'main'中:test.c:149:11:警告:函数'maximum_subarray'的隐式声明[-Wimplicit-function-declaration] int sum = maximum_subarray(arr,0,n-1,开始,结束); ^ ~~~~~~~~~~~~~~~
#include<stdio.h>
// find maximum sum subarray such that starting index present in left array
// and end index present in right array
int maxcross_subarray(int* arr, int low, int mid, int high, int &start, int &end)
{
// find maximum sum in left array which include mid index
int sum = 0;
int max_sum_left = (1<<31); // maximum value in negative
for (int i = mid; i >= low; i--)
{
sum += arr[i];
if (max_sum_left < sum) // update start index and left_sum
{
max_sum_left = sum;
start = i;
}
}
// find maximum sum in right array which include mid+1 index
sum = 0;
int max_sum_right = (1 << 31); // maximum value in negative
for (int i = mid + 1; i <= high; i++)
{
sum += arr[i];
if (max_sum_right < sum) // update end index and right sum
{
max_sum_right = sum;
end = i;
}
}
return max_sum_right + max_sum_left; // return total left+right sum
}
int maximum_subarray(int* arr, int low, int high, int &start, int &end)
{
if (low == high) // only one element in array
{
start = low;
end = low;
return arr[low];
}
int mid = (low + high) / 2; // mid index calculation
int s1, s2, s3; // starting index for 3 cases
int e1, e2, e3; // end index for 3 cases
// calculate max subarray such that complete array present in left half
int left_max = maximum_subarray(arr, low, mid, s1, e1);
// calculate max subarray such that complete array present in right half
int right_max = maximum_subarray(arr, mid+1, high, s2, e2);
// calculate max subarray such that max subarray present in both halves
int cross_max = maxcross_subarray(arr, low, mid, high, s3, e3);
// check for maximum sum
if (left_max > right_max && left_max>cross_max)
{
start = s1;
end = e1;
return left_max;
}
else if (right_max>left_max && right_max>cross_max)
{
start = s2;
end = e2;
return right_max;
}
else
{
start = s3;
end = e3;
return cross_max;
}
}
int main()
{
// test case 1
int arr[] = { -2, -5, 6, -2, -3, 1, 5, -6 };
int n = sizeof(arr) / sizeof(arr[0]);
int start, end;
int sum = maximum_subarray(arr, 0, n - 1, start, end);
printf("Array: ");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
printf("maximum subarray sum: %d\n", sum);
printf("Starting index: %d\n", start);
printf("end index: %d\n", end);
//test case 2
int arr1[] = { 2 , 3, 4, -7, 8 };
n = sizeof(arr1) / sizeof(arr1[0]);
sum = maximum_subarray(arr1, 0, n - 1, start, end);
printf("Array: ");
for (int i = 0; i < n; i++)
{
printf("%d ", arr1[i]);
}
printf("\n");
printf("maximum subarray sum: %d\n", sum);
printf("Starting index: %d\n", start);
printf("end index: %d\n", end);
return 0;
}