最大子段和
本文主要介绍了最大子段和的三种算法，比较时间性能
最大子段和
一.实验题目
给定由n个整数组成的序列(a1, a2, …, an)，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0
二.实验目的
- 深刻掌握动态规划法的设计思想并能熟练运用
- 理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果
三.实验要求
- 分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法
- 比较不同算法的时间性能
- 给出测试数据，写出程序文档
四.算法实现分析及结果
蛮力法
#include<bits/stdc++.h> using namespace std; int ans,m; void sum(vector<int> v) { for(int i=0;i<v.size();i++){ if(v[i]<0) continue; else{ ans=0; for(int j=i;j<v.size();j++){ ans+=v[j]; if(m<ans) m=ans; } } } } int main() { vector<int> v; int N; cin>>N; for(int i=0;i<N;i++){ int a; cin>>a; v.push_back(a); } sum(v); cout<<m; return 0; }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
+ 算法分析
+ 算法思想
遍历，从每一个非0的位置开始，将后面的数累加，如果累加和小于之前所计算的最大值，则ans记录为该值，直到循环结束
+ 时间复杂度分析
最大时间复杂度为循环n次，每次循环中再循环n-i次---->O(n)=n*(n-1)/2---->O($n^2$)
+ 实验结果分析
{% asset_img 最大子段和暴力.png 最大子段和暴力%}
+ 运行结果
{% asset_img 最大字段和暴力运行结果.png 最大字段和暴力运行结果%}
+ 分治法
+ ```c++
int MaxSum(int a[],int left,int right)
{
int sum=0,midSum=0,leftsum=0,rightsum=0;
int center,s1,s2,lefts,rights;
if(left==right) sum=a[left];
else{
center=(left+right)/2;
leftsum=MaxSum(a,left,center);
rightsum=MaxSum(a,center+1,right);
s1=0;lefts=0;
for(int i=center;i>=left;i--){
lefts+=a[i];
s1=max(s1,lefts);
}
s2=0;rights=0;
for(int j=center+1;j<=right;j++){
rights+=a[j];
s2=max(s2,rights);
}
midSum=s1+s2;
sum=max(midSum,max(leftsum,rightsum));
}
return sum;
}算法分析
算法思想
将序列划分为两份，递归求解左右两部分，然后计算一部分再左面，另一部分在右面的情况，最后选取三者最小即为ans
时间复杂度分析
当n==1时 T(n)=1
当n>1时 T(n)=2*T(n/2)+1—->O(n $log_2n$)
实验结果分析
运行结果
动态规划法
//只要前面的数的和不小于零加上下一个一定比下一个大 int MaxSum(int a[],int n) { int pre=0; int sum=0; for(int i=0;i<n;i++){ if(pre<=0) pre=a[i]; else pre+=a[i]; sum=max(sum,pre); } return sum; }算法分析
算法思想
满足最优性原理，设a 1,a 2,a 3,–,an是最长字段是起始位置到n的最长字段和，如果b 1, b 2,b 3,–,b n是起始位置到n-1的最大字段和，则b 1到an的和要大于a 1到a n，从而导致矛盾，所以满足最优性原理
状态方程：$b[j]=max(\sum_{k=i}^{j}a[k]) 0<=i<j$
——>>>当b[j-1]>0时,b[j]=b[j-1]+a[j],else b[j]=a[j] 选取其中的最值
只与前一项有关，用pre记录b[j-1]
时间复杂度
只需一层循环遍历一次—->O(n)
实验结果分析
运行结果
五.实验体会
计算最大子段和，首先利用了暴力法求解，两层循环结束，思路清晰，时间复杂度为平方级，然后用分治法，递归求解两部分，在两部分和公共部分三段中取最大值，即为结果时间复杂度为n*log级，最后是动态规划法，重点在于找到合适的状态转移方程，递推下去求出结果。动态规划型题首先得证明最优性原理，说明可以先求解子问题，该子问题解确定一个阶段，下一阶段解可以利用这一结果，避免了大量的重复计算.