Maximum Subarray Problem



[b]请大家帮忙看看，以下程序有什么问题。为什么运行不了？欢迎大家指正。

#include <stdio.h>
#include <stdlib.h>


struct tuple
{ int low;
int high;
int sum;
};


struct tuple FindMaxCrossingSubarray (int a1[], int low, int mid, int high);
struct tuple FindMaxSubarray (int a2[], int low, int high);


//找跨子列A[low..mid]和A[mid+1..high]的最大和子列

struct tuple FindMaxCrossingSubarray (int a1[], int low, int mid, int high)
{
int leftsum=-1000, rightsum=-1000;
int i, j, sum=0, maxleft, maxright;
struct tuple p1;

for (i=mid; i>=low; i--)
{
sum=sum+a1[i];
if (sum>leftsum)
{leftsum=sum;
maxleft=i;
}
}
//printf("%d, %d\n", maxleft, leftsum);


sum=0;
for (j=mid+1; j<=high; j++)
{
sum=sum+a1[j];
if (sum>rightsum)
{ rightsum=sum;
maxright=j;
}
}
// printf("%d, %d\n", maxright, rightsum);
//printf("%d, %d, %d\n",maxleft,maxright,leftsum+rightsum);
//return (maxleft,maxright,leftsum+rightsum);

p1.low=maxleft;
p1.high=maxright;
p1.sum=leftsum+rightsum;
return p1;

}



//找数列A[low..high]的最大和子列

struct tuple FindMaxSubarray (int a2[], int low, int high)
{
int mid;
int leftlow, lefthigh, leftsum, rightlow, righthigh, rightsum, crosslow, crosshigh, crosssum;
struct tuple p1;
struct tuple leftSubarray;
struct tuple rightSubarray;
struct tuple crossSubarray;

if (high==low)
{
p1.low=low;
p1.high=low;
p1.sum=a2[low];
return p1;
// return (low, high,a2[low]);
}

else mid=(low+high)/2;

leftSubarray=FindMaxSubarray (a2,low,high);

rightSubarray=FindMaxSubarray (a2,mid+1,high);

crossSubarray=FindMaxCrossingSubarray (a2, low, mid, high);

if (leftSubarray.sum>=rightSubarray.sum && leftSubarray.sum>=crossSubarray.sum)
return (leftSubarray);
else if (rightSubarray.sum>=leftSubarray.sum && rightSubarray.sum>=crossSubarray.sum)
return (rightSubarray);
else return (crossSubarray);

}

int main (void)
{
int A[16]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
struct tuple p1;
p1= FindMaxSubarray (A, 0, 15);
printf("The maximum subarray of A start at: %d, and end at: %d.\n", p1.low, p1.high);
printf("The maximum is: %d\n", p1.sum);


system ("pause");
return 0;
}
[解决办法]
leftSubarray=FindMaxSubarray (a2,low,high);
这里的high应该是mid