Algorithm:C++语言实现之求最大连续子数组(暴力法、分治法、分析法、动态规划法)
【摘要】 Algorithm:C++语言实现之求最大连续子数组(暴力法、分治法、分析法、动态规划法)
目录
求最大连续子数组
T1、code暴力法 O(n3)
T2、分治法 O( n*log(n) )
T3、分析法 O(n)
T4、动态规划法 O(n)
求最大连续子数组
给定一个数组A[0,…,n-1],求A...
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)
T2、分治法 O( n*log(n) )
将数组从中间分开,那么最大子数组要么完全在左半边数组,要么完全在右半边数组,要么跨立在分界点上。
完全在左数组、右数组递归解决。
跨立在分界点上:实际上是左数组的最大后缀和右数组的最大前缀的和。因此,从分界点向前扫,向后扫即可。
分治算法复杂度
T3、分析法 O(n)
逻辑推理的算法应用
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)
文章来源: yunyaniu.blog.csdn.net,作者:一个处女座的程序猿,版权归原作者所有,如需转载,请联系作者。
原文链接:yunyaniu.blog.csdn.net/article/details/81321112
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论(0)