脚本宝典收集整理的这篇文章主要介绍了第三章实验报告,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
1.1 问题描述:
给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时,定义子段和为0。
要求算法的时间复杂度为O(n)。
1.2 算法描述:
#include<bits/stdc++.h> using namespace std; int dp(int A[],int n){ int dp=0; int max=0; for(int i=0;i<n;i++){ if(dp>=0){ dp=dp+A[i]; } else{ dp=A[i]; } if(dp>max){ max=dp; } } return max; } int main(){ int n,i; int a[1000]={0}; cin>>n; for(i=0;i<n;i++){ cin>>a[i]; } cout<<dp(a,n)<<endl; return 0; }
1.3 问题求解:
1.3.1 根据最优子结构性质,列出递归方程式:
a[i] d[i+1]<=0;
d[i]= a[i]+d[i+1] d[i+1]>=0;
1.3.2 给出填表法中表的维度、填表范围和填表顺序:
一维数组
填表顺序为d[i]-->d[1]
从右往左
1.3.3 分析该算法的时间和空间复杂度:
时间复杂度为O(n)
空间复杂度为O(n)
1.4 心得体会:
通过这次实验我明白了动态规划的思路,与之前学过的分治法类似,也是将问题划分为若干个子问题,这时对D[n]的理解就很关键,也许一些简单问题根据生活常识可以没有章法的编程出来,但在面临一些复杂问题时还是需要我们有动态规划的思想来解决,通过对问题结构的分析,理清思绪,才能更容易着手。
以上是脚本宝典为你收集整理的第三章实验报告全部内容,希望文章能够帮你解决第三章实验报告所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。