Algorithm:C++语言实现之求最大连续子数组(暴力法、分治法、分析法、动态规划法)-阿里云开发者社区

开发者社区> 数字技术前瞻> 正文
登录阅读全文

Algorithm:C++语言实现之求最大连续子数组(暴力法、分治法、分析法、动态规划法)

简介: Algorithm:C++语言实现之求最大连续子数组(暴力法、分治法、分析法、动态规划法)

求最大连续子数组


给定一个数组A[0,…,n-1],求A的连续子数组,使得该子数组的和最大。

例如,数组: 1, -2, 3, 10, -4, 7, 2, -5;最大子数组:3, 10, -4, 7, 2


T1、code暴力法  O(n3)


时间复杂度O(n3)

image.png



T2、分治法   O( n*log(n) )


将数组从中间分开,那么最大子数组要么完全在左半边数组,要么完全在右半边数组,要么跨立在分界点上。

完全在左数组、右数组递归解决。

跨立在分界点上:实际上是左数组的最大后缀和右数组的最大前缀的和。因此,从分界点向前扫,向后扫即可。

分治算法复杂度

image.png

image.png





T3、分析法   O(n)


逻辑推理的算法应用

image.png





T4、动态规划法  O(n)


记S[i]为以A[i]结尾的数组中和最大的子数组则:S[i+1] = max(S[i]+A[i+1], A[i+1])

S[0]=A[0]

遍历i: 0≤i ≤n-1

动态规划:最优子问题

时间复杂度:O(n)

image.png




版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: