算法第三章上机实践报告

1.实践题目

7-2 最大子段和

2.问题描述

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

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

3.算法描述

#include<iostream>
using namespace std;
int MaxSum(int n, int*a){
 int sum = 0, b = 0, i;
 for(i=1; i <= n;i++){
  if (b > 0)
     b = b + a[i];
  else
     b = a[i];
  if (b > sum)
     sum = b;
 }
 return sum;
}

int main()
{
 int n;
 cin >> n;
 int i;
 int a[n+1];
 for(i=1; i<=n;i++){
  cin>>a[i];
 }
 cout<<MaxSum(n,a);

}

4.算法时间及空间复杂度分析

 我们的代码时间复杂度和空间复杂度都是O(n)。

5.心得体会

 此次上机实践有很大的收获，我和我的队友做的题是最大子段和，一开始我因为没看懂题目，所以一直在看书本上的内容，之后和队友进行了较长的沟通之后，我对最大子段和有了更深一层的理解，也成功在队友的合作下敲完了代码。我觉得最大子段和的递归方程式还是比较容易理解的，就是一定要理清b和sum之间的关系和区别，sum就是要求得的最终结果，而b则是b[j-1]+a[j]与a[j]比较结果更大的值，b有可能会是sum的结果，如果最终b的值是最大的，则将b值赋于sum，从而输出结果sum。理解了公式以及b和sum的含义之后解题就变得十分容易了。

算法第三章上机实践报告

原文：https://www.cnblogs.com/zhouhaoyu/p/11704682.html