编程珠玑 求解最大字串和
?
编程珠玑8.4节讲扫描算法,我看了半天都没看明白,最后自己写了一遍,终于搞懂了,把它记下来,以免今后忘了。
首先,书上的算法是这样写的:
?12345maxsofar
=
0
maxendinghere
=
0
for
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;
}