算法研究(四) 一维模式识别
题目:这是一个一维模式识别问题,问题的输入是一个具有n个浮点数据字的向量x,其输出是在输入的任何相邻子向量中找出的最大和,例如,如果输入向量包含下面10个元素:
图中显示了找出的子向量。
按照时间复杂度由大到小,以下给出解此题的四种算法:
? 算法一:三重循环比较 O(n3)
伪码如下:
伪码如下:
maxvalue = 0;maxendvalue = 0;for (i = 0; i < n; ++i) { maxendvalue = max(maxendvalue + data[i], 0); maxvalue = max(maxvalue, maxendvalue);}是不是很神奇,呵呵~~