算法第三章上机实践报告

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法第三章上机实践报告，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含692字，纯文字阅读大概需要1分钟。

内容图文

1、实践题目：

最大子段和

2，问题描述：

 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。

要求算法的时间复杂度为O(n)。

3、算法描述：

定义两个数组a,b，a表示要输入的序列,b表示序列的子段和(比如b[3]表示a[1],a[2],a[3]的最大子段和），然后进行判断，如果前面的最大子段和大于0，则加上改最大子段和，若前面的最大子段和小于0，则不加，最后在判断该序列是否全部为负数，若是则输出0，若不是，则输出b[i]。

4、空间复杂度分析：

空间复杂度为O（n）。

5、代码描述：

#include <iostream>;
using namespace std;

int a[10000],b[10000];
int num=0;
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
b[i]=max(a[i],b[i-1]+a[i]);
num=max(num,b[i]);
}
cout<<num;
return 0;
}

6、心得体会：

该题运用动态规划的思想解题，而且不会太难理解，与队友做完这道题后，感觉对自己理解动态规划的思想有所帮助。

原文：https://www.cnblogs.com/-Kdj/p/9905388.html

内容总结

以上是互联网集市为您收集整理的算法第三章上机实践报告全部内容，希望文章能够帮你解决算法第三章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---