编程珠玑 求解最大字串和
?
编程珠玑8.4节讲扫描算法，我看了半天都没看明白，最后自己写了一遍，终于搞懂了，把它记下来，以免今后忘了。
首先，书上的算法是这样写的：
?12345
maxsofar = 0maxendinghere = 0for i=[0 n)????maxendinghere = max(maxendinghere + x[i], 0)????maxsofar = max(maxsofar, maxendinghere)?
这个max so far和max ending here究竟表示什么呢？
先来看我写的程序的输出：
输入：{31, -41, 59, 26, -53, 58, 97, -93, -23, 84}
输出：
?
其中Accu就是maxsofar，而Max就是maxending。
原理是这样的：
我们把成为最大字串和的字串SubSeq看成两部分：
前一部分为整个字串和贡献的值要大于0。
后一部分不能减少前一部分的值。
比如：{59, 26, -53}是前一部分，而{58, 97}是后一半。
好，现在再来看算法：
每次将x[i]加到Accu上，看Accu是不是减小了；
如果是，就先暂时不要x[i]，直到Accu比它达到过的最大值还要大，这时就可以把暂时不要的的所有x[..]加到字串中，因为它们对字串的贡献>0。
而Max记录的就是Accu达到过的最大值。
更多信息请查看?java进阶网?http://www.javady.com
废话不多说了，直接上代码：
?12345678910111213141516171819202122232425262728293031323334353637#include <stdio.h>#include <limits.h>#include <math.h>#include <string.h>?int seq_start = 0;int seq_end = 0;?int max_sum(int x[], int n){????int max = INT_MIN, temp_sum = 0;????bool hasNewStart = true;????printf("No Accu? Max? SPos EPos\tSubSeq\n");????for (int i = 0; i < n; i++)????{????????temp_sum += x[i];????????if(temp_sum > max)????????{????????????max = temp_sum;????????????seq_end = i;????????????if (hasNewStart)????????????{????????????????seq_start = i;????????????????hasNewStart = false;????????????}????????}????????else if (temp_sum < 0)????????{????????????temp_sum = 0;????????????hasNewStart = true;????????}????????char * tmp_str = arr2str((int *) &(x[seq_start]), seq_end - seq_start + 1);????????printf("%2d %4d %4d %3d %3d\t%s \n", i, temp_sum, max, seq_start, seq_end, tmp_str);????????delete [] tmp_str;????}????return max;}