求最大和连续子向量问题的算法分析(二)
据最后的结果得出，和最大的连续子向量即为 x[2 . . . 6],总和为187。
该算法只扫描了输入向量一遍，则该算法的复杂度为 O(n)。这是一个线性算法，已经是最优的了。
3 问题来历
该问题出现在布朗大学的 Ulf Grenander 所面对的一个模式识别问题中,问题的最初形式为下面的二维形式。
“给定 n × n 的实数数组,求出矩形子数组的最大总和。”
在二维形式的问题中，最大总和子数组是数字图像中某种特定模式的最大似然估计量。因为二维问题的求解需要太多时间，所以 Grenander 将它简化为一维问题，以深入了解其结构。
最近看到这个问题问题才想起来,两年前毕业找工作的时候，就被一个面试官问到过这个二维问题。那时胡乱讲了一通，最后面试当然就悲剧了。后面找个空闲时间再好好思考一下吧。