算法导论寻找最大子数组 (一)

算法导论在讲解分治算法中第二个典型的例子，在一个数组中寻找最大子数组。即在这个数组中找到连续加和最大的部分！
我们先分析该问题，能够发现如果将数组分成两部分，寻找到每一部分的最大子数组和跨越两部分的最大子数组，即为该问题的完全解。

我们发现最复杂部分是跨越两部分的最大子数组，我们先来解决这部分的问题。

首先先看代码：

[cpp]

[cpp]
int Find_MAX_CROSSING_SUBARRAY(int *A,int low,int mid,int high,int& max_left,int& max_right,int& max_value)
{
int left_sum= -1000000;//不可能的最小值
int sum = 0;

for(int i= mid;i>low;i--)
{
sum = sum+A[i];
if(sum>left_sum)
{
left_sum = sum;
max_left=i;
}
}

int right_sum = -1000000;//不可能的最小值
sum =0;

for(int j=mid+1;j {
sum = sum+A[j];
if(sum>right_sum)
{
right_sum = sum;
max_right =j;
}
}

max_value = left_sum+right_sum;
return 0;
}

int Find_MAX_CROSSING_SUBARRAY(int *A,int low,int mid,int high,int& max_left,int& max_right,int& max_value)
{
int left_sum= -1000000;//不可能的最小值
int sum = 0;

for(int i= mid;i>low;i--)
{
sum = sum+A[i];
if(sum>left_sum)
{
left_sum = sum;
max_left=i;
}
}

int right_sum = -1000000;//不可能的最小值
sum =0;

for(int j=mid+1;j {
sum = sum+A[j];
if(sum>right_sum)
{
right_sum = sum;
max_right =j;
}
}

max_value = left_sum+right_sum;
return 0;
}

从算法上看到，我们依然放入了两个不可能的哨兵值。上面代码中 每一行都已经很清晰，这里就不做分析了，不懂的童鞋可以留言。然后我们来写函数的递归部分，退出递归的条件是关键，试想如果low和high是同一个值我们该如何求最大子数组，这当然是废话，直接返回这个值就好了，所以算法就这样搞定了，然后贴出代码：

[cpp]
int Find_MaxiMum_SubArray(int *A,int low,int high,int& max_left,int& max_right,int& max_value)
{
if(high==low)
{
max_left = low;
max_right = high;

max_value = A[low];
}
else
{
int mid=(low+high)/2;

int tmp_left_low;
int tmp_left_high;
int tmp_left_sum;

Find_MaxiMum_SubArray(A,low,mid,tmp_left_low,tmp_left_high,tmp_left_sum);

int tmp_right_low;
int tmp_right_high;
int tmp_right_sum;

Find_MaxiMum_SubArray(A,mid+1,high,tmp_right_low,tmp_right_high,tmp_right_sum);

int tmp_cross_low;
int tmp_cross_high;
int tmp_cross_sum;

Find_MAX_CROSSING_SUBARRAY(A,low,mid,high,tmp_cross_low,tmp_cross_high,tmp_cross_sum);

if ((tmp_left_sum>=tmp_right_sum)&&(tmp_left_sum>=tmp_cross_sum))
{
max_left = tmp_left_low;
max_right = tmp_left_high;
max_value = tmp_left_sum;
}
else if((tmp_right_sum>=tmp_left_sum)&&(tmp_right_sum>=tmp_cross_sum))
{
max_left = tmp_right_low;
max_right = tmp_right_high;
max_value = tmp_right_sum;
}
else
{
max_left = tmp_cross_low;
max_right = tmp_cross_high;
max_value = tmp_cross_sum;
}

}

return 0;
}

int Find_MaxiMum_SubArray(int *A,int low,int high,int& max_left,int& max_right,int& max_value)
{
if(high==low)
{
max_left = low;
max_right = high;

max_value = A[low];
}
else
{
int mid=(low+high)/2;

int tmp_left_low;
int tmp_left_high;
int tmp_left_sum;

Find_MaxiMum_SubArray(A,low,mid,tmp_left_low,tmp_left_high,tmp_left_sum);