电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

最大连续子序列求和问题VIP免费

最大连续子序列求和问题_第1页
1/1
最大连续子序列求和问题什么是最大连续子序列和问题?问题描述:给定一个序列(整数或浮点数),求出其中连续的子序列和最大的那一个。例:序列{-101234-5-2337-21},其最大的连续子序列为{1234}或{37},最大和为10.方法一:暴力求解最最普通的方法,效率十分低,一般不会用到,这里简单介绍。直接两个for循环枚举子序列的首尾,再来一个for循环计算首尾之间的序列和,计算所有的序列和,找到最大值。时间复杂度:O(n^3)方法二:预处理暴力求解第一种方法为什么这么慢,原因之一是每次都要计算首尾之间的序列和。基于这个考虑,我们可以对数据进行预先处理:读入数据时使用一个数组SUM[i]来记录前i项数据之和。用这种方法,只需要两个for循环枚举子序列的首尾,利用SUM数组计算子序列和,找到最大值。时间复杂度:O(n^2)方法三:分治法求解把序列分成左右两部分,一般对半分,数量不等也没关系。最大子序列和的位置存在三种情况:1、完全在左半部分;2、完全在右半部分;3、跨越左右两部分。分别求出左半部分的最大子序列和、右半部分的最大子序列和、以及跨越左右两部分的最大子序列和,三者中的最大者就是要求的。如何求三部分的最大子序列和呢?左半部分的最大子序列和,可把左半部分作为新的输入序列通过该算法递归求出。右半部分的最大子序列和同理。接下来就是求解跨越左右两部分的最大子序列和,也就是求出包含左半部分中最右边元素的子序列的最大和,和包含右半部分中最左边元素的子序列的最大和,将两者相加即为跨越左右两个部分的最大子序列和。方法四:动态规划这是最常见的方法了,简单有效,好理解。状态转移方程:sum[i]=max{sum[i-1]+a[i],a[i]}.(sum[i]记录以a[i]为子序列末端的最大序子列连续和)其实完全可以不用开数组,累计sum直到sum+a

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

最大连续子序列求和问题

确认删除?
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群