Java教程

算法第三章实践报告

本文主要是介绍算法第三章实践报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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 心得体会

动态规划相较于前两章更难理解一些,但核心思想与分治法有相似之处,都是通过将主问题分解为子问题然后自底向上求解,但关键在做题时要理清动态规划递归方程式的意思,以及表格的填写,这样才能透彻地解决问题。学好动态规划仍有好些路要走,我还要多做题多理解才行!

这篇关于算法第三章实践报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!