1、实践题目
7-2 最大子段和
2、问题描述
给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。
要求算法的时间复杂度为O(n)。
3、算法描述
这一题采用动态规划的方法，首先写出递归方程：b[ i ] = max { b[ i-1] + a[ i ] , a[ i ] }
定义一个整型数组a[ n ]获取输入的数列，一个整型变量b记录以当前整数结尾的最大子段和，一个整型变量sum记录整个数列的最大子段和。
从数列的第一个元素开始，每到一个数就计算一次递归方程，得到的b跟sum比较后记录sum。
实现代码：
#include<iostream>
using namespace std;
int maxsum(int *a, int n)
{
int sum=0, b=0;
int i;
for(i=1;i<=n;i++){
if(b>0) 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(a,n);
}
4、算法时间及空间复杂度分析
时间复杂度：主函数有一个for循环输入，计算最大子段和的函数也只有一个for循环，循环中只有比较和赋值，所以算法的时间复杂度是O(n)
空间复杂度：一个长度为n的数组，和两个整型变量，所以空间复杂度是O(n)
5、心得体会
动态规划法是从小规模问题开始，得到的结果为下一步计算提供条件，就这样一步步往后算。运用动态规划方法求解问题最主要是写出要用的递归方程，然后写出求解递归方程的代码。动态规划发可以让解决问题变得简单，短短的几行节省了时间和空间。
算法第三章上机实践报告
原文：https://www.cnblogs.com/sergio415/p/11694300.html
