雅乐网

计算机技术、学习成长

计算机 » 算法 » 最大子列和问题

最大子列和问题

给定K个整数组成的序列{ N1, N2, …, NK },“连续子列”被定义为{ Ni, Ni+1, …, Nj },其中 1 <= i <= j <= K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。

遍历算法 O(n^3)的算法

这种方法遍历所有的序列和。

遍历算法 O(n^2)的算法

上面的算法中,一个子列加上一个元素,并没有直接利用之前子列的和,而是重新计算。可以利用子列的和加上新来的元素,算法的复杂度为O(n^2)

 分而治之的O(nlogn)的算法

找最大子列,可能在左半边,也可能在右半边,也可能跨越了中间。

scrn20150205120719

代码如下:

时间复杂度 T(n) = 2T(n/2) + n ,由主定理可知,时间复杂度为O(nlogn)

复杂度O(n)的算法

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/max_sub_seq_sum.html

上一篇:

下一篇:

我要评论

验证码*: 8 + 0 =