我本想写一篇内网在开发环境关于 solr 的一些问题的解决办法,鉴于坑比较多且牵涉较广。 另外也是因为 If it ain't broke, don't fix it
这个原则,所以此篇我打算分享给大家一个算法。
问题的输入是具有 n
个浮点数的向量 x
,输出是输入向量的任何连续子向量中的最大和。例如,如果输入向量包含下面 10
个元素:
| 31 | -41 | 59 | 26 | -53 | 58 | 97 | -93 | -23 | 84 |
那么该程序的输出为 x[2..6]
的总和,即 187
。对于这个问题,我直接给出最优算法,其伪代码如下,此算法源自《编程珠玑》:
maxsofar = 0
maxendinghere = 0
for i = [0, n]
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
该代码比较复杂,但十分简短,运行起来也很快。预计这个问题日常开发也会碰到。