算法第三章上机实践报告
实践题目
7-2 最大子段和 (40 分)
给定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
问题描述求一段无规律整数的最大子段和。算法描述
#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;
int a[100];
for(int i=1; i<=n; i++){
cin >> a[i];
}
int sum = 0;
int b = 0;
for (int i = 1; i <= n; i++){
if (b>0){
b += a[i];
}else
b = a[i];
if (b > sum){
sum = b;
}
}
cout<<sum;
return 0;
}
算法时间及空间复杂度分析
算法思想：
运用了动态规划的思想来解决最大子段和问题：
通过遍历累加这个数组元素，定时的更新最大子段和，
如果当前累加数为负数，直接舍弃，重置为0,然后接着遍历累加。
时间复杂度:只有一个for循环所以时间复杂度为O(n)。 空间复杂度：有一个最大存100个数据的数组，所以空间复杂度也为O(n)。
心得体会
通过老师的提问，搞清楚了编程过程中的变量的实际意义，这是很重要的。如果不清楚一个数组或者变量的用途，那这个代码就难以理解。