算法第三章上机实践报告

给定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)。

心得体会

通过老师的提问，搞清楚了编程过程中的变量的实际意义，这是很重要的。如果不清楚一个数组或者变量的用途，那这个代码就难以理解。