刚开始学C的数据结构，有个关于递归的算法想问一下问题是这样的：
已知给定的一个数字序列（诸如：3，-2，8，4，5，-9......)，并且这个序列只包含有限的元素个数，试问：
在这个数列中取出其中的连续N个数，使其和为最大，现在的问题就是要求这个最大和为多少！
这个问题取自（Mark Allen Weiss）所著的《Data Structures and Algorithm Analysis in C 》
这两天我刚开始看这本书，当然我看的那个是中文版，当时书上一共给出了4中算法，前两种和最后一种我都看懂了，
就是中间有个关于递归的算法，我不是很理解，我总觉得这个递归不可能成功，因为递归的尽头总是必须调用一个已知的结论，或者是一个本身不再是递归属性的函数，然后将最终的这个值层层返回到开始第一次调用递归的的函数的出口，这样的递归才是有意义的。而第三种方法具体的提法，我这里引用的是英文原版上的内容：（在给出最终的代码之前，作者给出了关于第三种算法的实施的思想，所以建议大家先看看它解决这个问题的思想是什么，然后再看看代码，可能也更容易弄懂一些，否则会觉得问题来的很唐突）：（文献引用如下）
另外如果觉得字太小，看不清我在这里另外上传了一个附件：
Algorithm 3
In our case, the maximum subsequence sum can be in one of three places. Either it occurs entirely in the left half of the input, or entirely in the right half, or it crosses the middle and is in both halves. The first two cases can be solved recursively. The last case can be obtained by finding the largest sum in the first half that includes the last element in the first half and the largest sum in the second half that includes the first element in the second half. These two sums can then be added together. As an example, consider the following input:
First Half Second Half
----------------------------------------
4 -3 5 -2 -1 2 6 -2
The maximum subsequence sum for the first half is 6 (elements a1 through a3), and for the second half is 8 (elements a6 through a7).
The maximum sum in the first half that includes the last element in the first half is 4 (elements a1 through a4), and the maximum sum in the second half that includes the first element in the second half is 7 (elements a5 though a7). Thus, the maximum sum that spans both halves and goes through the middle is 4 + 7 = 11 (elements a1 through a7).
We see, then, that among the three ways to form a large maximum subsequence, for our example, the best way is to include elements from both halves. Thus, the answer is 11. Figure 2.7 shows an implementation of this strategy.
int
max_sub_sequence_sum( int a[], unsigned int n )
{
return max_sub_sum( a, 0, n-1 );
}
int
max_sub_sum( int a[], int left, int right )
{
int max_left_sum, max_right_sum;
int max_left_border_sum, max_right_border_sum;
int left_border_sum, right_border_sum;
int center, i;
/*1*/ if ( left == right ) /* Base Case */
/*2*/ if( a[align=left] > 0 )
/*3*/ return a[align=left];
else
/*4*/ return 0;
/*5*/ center = (left + right )/2;
/*6*/ max_left_sum = max_sub_sum( a, left, center );
/*7*/ max_right_sum = max_sub_sum( a, center+1, right );
/*8*/ max_left_border_sum = 0; left_border_sum = 0;
/*9*/ for( i=center; i>=left; i-- )
{
/*10*/ left_border_sum += a[i];
/*11*/ if( left_border_sum > max_left_border_sum )
/*12*/ max_left_border_sum = left_border_sum;
}
/*13*/ max_right_border_sum = 0; right_border_sum = 0;
/*14*/ for( i=center+1; i<=right; i++ )
{
/*15*/ right_border_sum += a[i];
/*16*/ if( right_border_sum > max_right_border_sum )
/*17*/ max_right_border_sum = right_border_sum;
}
/*18*/ return max3( max_left_sum, max_right_sum,
max_left_border_sum + max_right_border_sum );
}
NST3Ywi1.rar
