算法第三章上机实践报告
2021/10/23 12:09:36
本文主要是介绍算法第三章上机实践报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最大子段和
1.1问题描述:给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时,定义子段和为0。
要求算法的时间复杂度为O(n)。
输入格式:
输入有两行:
第一行是n值(1<=n<=10000);
第二行是n个整数。
输出格式:
输出最大子段和。
输入样例:
在这里给出一组输入。例如:
6
-2 11 -4 13 -5 -2
结尾无空行
输出样例:
在这里给出相应的输出。例如:
20
结尾无空行
1.2 算法描述(动态规划)
添加一个一维数组b[n+1],初始化为0,其中b[j](1<=j<=n)表示以a[j]结尾的最大子段和,数组b[n+1]中的最大值即为所求题目中数组a[n+1]的最大子段和。
1.3问题求解
1
1.4 递归方程式
b[j]=min{b[j-1]+a[j],a[j]} 1<=j<=n
1.5 填表
b[1] |
b[2] |
b[3] |
… |
b[j] |
… |
b[n-1] |
b[n] |
表为一维表格;填表范围为1-n;填表顺序是从b[1]填到b[n].
1.6 算法的复杂度
时间复杂度:O(n);
空间复杂度:O(n);
1.7 心得体会
做编程题时,不只要把题做出来,还要并明白自己的算法是什么。比喻动态规划算法,在做这类题的同时清楚自己的递归方程是什么,是非常重要的。
2对动态规划算法的理解和体会
动态规划算法是经典的最优值寻找算法,算法的每一步都会考虑是否全局最优。它是将待求解问题分成若干个子问题,求解子问题的最优解,最后一个子问题的最优解就是初始问题的解。对于重叠子问题,为了减少运算,对每个子问题只求解一次,将子问题不同阶段的不同状态保存在一个二维数组中。
我认为动态规划算法的难点在于找到初始题的子问题是什么,以及知道递归方程是什么和对边界条件的判断。
这篇关于算法第三章上机实践报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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题)