算法第三章实践报告
2021/10/27 1:10:43
本文主要是介绍算法第三章实践报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.1 问题描述
7-1 最大子段和 (25 分)给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时,定义子段和为0。
要求算法的时间复杂度为O(n)。
1.2 算法描述
设一个数组a[ ],用于存放n个数,定义一个整型sum存放最大和,定义一个整型b用于计算最大子段和。
用for语句访问数组,当b<0时,可将它直接赋值为a[i];
当b>0时,如果加上a[i]后小于0,就赋值a[i],大于零就和sun比较,如果比较后sum<b,就另sum=b,否则不变。
1.3 问题求解:
1.1.1 根据最优子结构性质,列出递归方程式,
b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n
1.1.2 给出填表法中表的维度、填表范围和填表顺序。
一维a[j]数组,一维b[j]数组,填表范围由0到j,填表顺序从左到右
1.1.3 分析该算法的时间和空间复杂度
本题算法实现只需要循环n次,时间复杂度为O(n), 空间复杂度也为O(n)。
1.4 心得体会
动态规划相较于前两章更难理解一些,但核心思想与分治法有相似之处,都是通过将主问题分解为子问题然后自底向上求解,但关键在做题时要理清动态规划递归方程式的意思,以及表格的填写,这样才能透彻地解决问题。学好动态规划仍有好些路要走,我还要多做题多理解才行!
这篇关于算法第三章实践报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)