最大连续子序列求和问题

最大连续子序列求和问题最大连续子序列求和问题什么是最大连续子序列和问题？问题描述：给定一个序列（整数或浮点数），求出其中连续的子序列和最大的那一个。例：序列{-101234-5-2337-21}，其最大的连续子序列为{1234}或{37}，最大和为10.方法一：暴力求解最最普通的方法，效率十分低，一般不会用到，这里简单介绍。直接两个for循环枚举子序列的首尾，再来一个for循环计算首尾之间的序列和，计算所有的序列和，找到最大值。时间复杂度：O(n^3)方法二：预处理暴力求解第一种方法为什么这么慢，原因之一是每次都要计算首尾之间的序列和。...

最大连续子序列求和问题什么是最大连续子序列和问题？问题描述：给定一个序列（整数或浮点数），求出其中连续的子序列和最大的那一个。例：序列{-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 练习题：杭电oj1003

                    本文档为【最大连续子序列求和问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

你可能还喜欢

最新资料

资料动态

专题动态

仙人指路88

暂无简介~

格式：doc

大小：15KB

软件：Word

页数：0

分类：小学语文

上传时间：2021-10-16

浏览量：3

热点搜索

【心理学】电影是普通工人的精神分析室——或曰：镜像与梦--李孟潮_495 党支部委员候选人登记表三爪自定心卡盘的基础尺寸和参数考研英语一大作文模板中华人民共和国主席令第13号中华人民共和国安全生产法《盗草》教案-02 作物抗逆性的基因工程研究进展资料土地翻耕工程报验表格山东省新高考联合质量测评2022-2023学年高一下学期3月联考英语试题【合同管理】第四章旅游合同法【精品】2,学科渗透教案.doc - 《小池塘》第二课时82 铵根离子离子浓度比较宋鸿兵简历_宋鸿兵简介_中国讲师网江南大学2011级各类学分要求【心理学】电影是普通工人的精神分析室——或曰：镜像与梦--李孟潮_495 党支部委员候选人登记表三爪自定心卡盘的基础尺寸和参数考研英语一大作文模板中华人民共和国主席令第13号中华人民共和国安全生产法《盗草》教案-02 作物抗逆性的基因工程研究进展资料土地翻耕工程报验表格山东省新高考联合质量测评2022-2023学年高一下学期3月联考英语试题【合同管理】第四章旅游合同法【精品】2,学科渗透教案.doc - 《小池塘》第二课时82 铵根离子离子浓度比较宋鸿兵简历_宋鸿兵简介_中国讲师网江南大学2011级各类学分要求