Maximum Subarray Problem

This post last edited by the lj_suxin on 2013-07-18 20:48:25 <> Given an array A, we want to find the nonempty, contiguous subarray of A whose values ??have the largest sum. This problem is called the maximum subarray problem. For example, let A [16] = {13, -3, -25,20, -3, -16, -23 , 18,20, -7,12, -5, -22,15, -4,7}, and the maximum subarray of A is {18,20, -7,12} .

The pseudocode of the maximum subarray problem is as following:



[b] Please help us to see what is the problem the following procedure. Why not run? Welcome to correct me.

# include
# include


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);


/ / find a cross-subsequence A [low .. mid] and A [mid +1 .. high] the maximum and sub-columns

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;

}



/ / find the series A [low .. high] the maximum and sub-columns

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;
}
------ Solution ----------------------------------- ---------
leftSubarray = FindMaxSubarray (a2, low, high);
Here's high should be mid
------ For reference only ---------------------------- -----------
very grateful, which under the right!