第3章实验总结

2021/10/26 23:12:01

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

1.实践题目名称:最大子段和

 

2.问题描述:给定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
结尾无空行   3.算法描述

#include <iostream>
using namespace std;

int a[10000];
int b[10000];
int n;

int maxnum()
{
int c=0;
b[0]=0;
for(int i=1; i<=n; i++)
{
b[i]=max(b[i-1], 0)+a[i-1];
c=max(b[i], c);
}
return c;
}

int main()
{ cin>>n;
for(int i=0; i<n; i++){
cin>>a[i];
}
int d = maxnum();
cout<<d<<endl;
return 0;
}

 

1.1.1 根据最优子结构性质,列出递归方程式:b[i]=max(b[i-1], 0)+a[i-1];c=max(b[i], c);

 

1.1.2 给出填表法中表的维度、填表范围和填表顺序。

表的维度:一维;填表范围:从a[0]开始填,填入a[i]的值;填表顺序:从左往右。

 

1.1.3算法时间复杂度和空间复杂度的分析

时间复杂度:O(n),因为只遍历了一次数组

空间复杂度:O(n),因为只用了一维表

 

4.心得体会

在做题之前,我去看了之前一直没时间看的北航的视频,了解了动态规划的思想,题解是小伙伴想出来的,她教会了我,然后我就自己打代码出来。至此,对动态规划的思想了解更深。

 

5.对动态规划的理解

动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。

我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。



这篇关于第3章实验总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程