Python实现最大子序和的方法示例

系统 1715 0

描述

给定一个序列(至少含有 1 个数),从该序列中寻找一个连续的子序列,使得子序列的和最大。
例如,给定序列 [-2,1,-3,4,-1,2,1,-5,4],
连续子序列 [4,-1,2,1] 的和最大,为 6。

我 v1.0

测试结果如下:

Python实现最大子序和的方法示例_第1张图片  

本地运行时间为14.7s,说明我的方法太粗暴了。应该寻找更好的算法。

 

我 优化后v1.1。优化方案,去掉sums数组,节省空间。但时间复杂度仍然不变。

仍然只通过200/202测试用例,仍然超出时间限制。但本地运行时间为8.3s。有进步。

别人,分治法。时间复杂度O(NlogN)

将输入的序列分成两部分,这个时候有三种情况。
1)最大子序列在左半部分
2)最大子序列在右半部分
3)最大子序列跨越左右部分。

前两种情况通过递归求解,第三种情况可以通过。

分治法代码大概如下,emmm。。。目前还没有完全理解。

动态规划算法,时间复杂度为O(n)。
分析:寻找最优子结构。

Oh!My god!!! !!!!!!!!运行只花了0.2s!!!!!!!!!!!!!!!这也太强了吧!!

Python实现最大子序和的方法示例_第2张图片  

优化后,运行时间0.1s.

其中

sum += nums[i] 必须紧挨。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论