算法第三章上机实践报告
一、 实践题目
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二、 问题描述
输入一个数，表示接下来输入的数组元素个数，第二行输入所有元素，求出他们的最大子段和（如果都是负数就输出0）。
相当于，从第一个数开始，往后加数，如果是正数就说明这个子段是“有用的”反之“对最大子段没有贡献”。只要判断每次以最后一个数为结尾和前一个数结尾的大小，取大的，递归赋给一个记录用的变量即可。
三、 算法描述
1、动态规划
for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
maxn=max(maxn,dp[i]);
}
从第一个数字开始，先赋初值0给dp数组和记录用的变量maxn，dp[i]为以第i个数字结尾的最大子段和。每次dp[i]都取数组第i个数和dp[i-1]加上目前指向的这个数中较大的那个（意义在于，如果目前指向的那个数比dp[i-1]加上目前指向的这个数还大，说明之前的子段和是负数，没有贡献不取）。而“maxn=max(maxn,dp[i])”就是筛选掉负数，若为正，取最大的子段和（dp数组储存着分别以每个数为结尾的最大子段和）。
2、判断输出
if(maxn) cout<<maxn<<endl;
else cout<<0<<endl;
若maxn为正数则得到最大子段和输出，否则（maxn为0或负数），数组全为负数或者最大子段和即为0，按要求输出0。
3、完整代码
#include<iostream>
#include<algorithm>
using namespace std;
int n,maxn;
int a[10005],dp[10005];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
maxn=max(maxn,dp[i]);
}
if(maxn) cout<<maxn<<endl;
else cout<<0<<endl;
return 0;
}
四、 算法时间及空间复杂度分析
for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
maxn=max(maxn,dp[i]);
}
循环递归调用n次，动态规划问题一般时间复杂度为O(n)或者O(n^2)，显然在这里是O(n)；
解这道题中，用到了dp数组和maxn变量作为辅助，空间复杂度同样为O(n)。
五、 心得体会
抓住问题的关键，理清解题思路，一道看似“很难”的题目其实很“简单”。尤其是动态规划问题，不断动态地自下而上添加新的元素得到结果，最后解决问题。
虽然思路想出来了，有时候还是不知道怎么下手去敲代码，反映了自己做题数量太少，打代码地时间和次数太少，还停留在空想地阶段，这是一个大问题，亟待改正和提高。
队友很强，有时候会比较依赖队友，应该先自己思考后再与队友讨论才能够有所提高。