实验报告
课程名称 算法分析与设计 实验项目名称 最大字段和问题 班级与班级代码 实验室名称（或课室） 实验楼802 专 业： 计算机科学与技术 任课教师： 李绍华 学 号： 姓 名： 实验日期： 2016年11月25日
广东财经大学教务处 制
姓名 实验报告成绩
评语：
指导教师（签名） 年 月 日
说明：指导教师评分后，实验报告交院（系）办公室保存。
一、实验目的
(1)能够熟悉最大字段和问题这个算法
(2)分别使用三种不同算法：暴力算法、分治算法、动态规划算法，体会其算法思想并比较时间复杂度。
二、实验设备
硬件： P4 2.0G 1G内存60G 硬盘以上电脑 软件： C 、C++编程环境，Java 编程环境，windows7
三、问题与算法描述
1、问题描述
给定由n 个整数（可能为负整数）组成的序列a1、a2、……a n ，求该序列形如∑a k 的字段和的最大值。当所有整数均为负整数时定义其最大字
k =i j
段和为0。依次定义，所求的最优值为max{0，2、算法描述 BF 算法
1
a k }。 max ∑k =i
j
对于起点 i，遍历所有长度为1,2, …,n-i+1的子区间和，遍历所有的字 段，找出最大字段和。 分治算法
求子区间及最大和，从结构上是非常适合分治法的，因为所有子区间 [start, end]只可能有以下三种可能性: 1.在[1, n/2]这个区域内 2. 在[n/2+1, n]这个区域内
3. 起点位于[1,n/2],终点位于[n/2+1,n]内
以上三种情形的最大者，即为所求. 前两种情形符合子问题递归特性，所 以递归可以求出. 对于第三种情形，则必然包括了n/2和n/2+1两个位置， 这样就可以利用第二种穷举的思路分别向左右扩张求出。 动态规划
扩展到二维空间令b[j]表示以位置 j 为终点的所有子区间中和最大的一 个子问题:如j 为终点的最大子区间包含了位置j-1, 则以j-1为终点的最 大子区间必然包括在其中，如果b[j-1] >0, 那么显然b[j] = b[j-1] + a[j]，用之前最大的一个加上a[j]即可，因为a[j]必须包含；如果 b[j-1]
3、算法时间复杂性分析
BF 算法：经过两次嵌套循环时间复杂度：O(n2)
分治算法：每递归一次需logn ，全部需要n 次运算量，时间复杂度：O(nlogn)动态规划算法：只经历了一次循环，时间复杂度：O(n)
四、实验调试过程中出现的问题
实验过程中，主要遇到了两个问题，随机函数和时间计算函数不知如何进行，虽然之前在以前的课程中学习过，但是由于时间长已经忘记，通过查阅和同学帮助最终解决。 五、实验结果
1. 源代码
package 算法实验2;
import java.util.Random;
public class Maxfield { static int a [] =new int [1001];
public static void main(String[] args ) { // TODO Auto-generated method stub Random ran =new Random(); for (int i =1;i
System. out .print("" );
}
long starttime = System.nanoTime (); int sum1= maxSum1();
long endtime = System.nanoTime (); long starttime1 = System.nanoTime (); int sum2=maxSum2(1,a . length -1); long endtime1 = System.nanoTime (); long starttime2 = System.nanoTime (); int sum3=maxSum3();
long endtime2 = System.nanoTime ();
System. out .println(" BF算法所求最大字段和为： "+sum1+" BF" +(endtime -starttime )); System. out .println(" 分治算法所求最大字段和为 ：" +sum2+" " +(endtime1-starttime1)); System. out .println(" 动态规划所求最大字段和为： "+sum3+" " +(endtime2-starttime2));
}
public static int maxSum1(){ long = System.currentTimeMillis (); int n =a . length -1; int sum =0;
int =0;int =0; for (int i =1;i
for (int j =i ; j sum ){ sum =thissum ; besti =i ;
bestj = j ;
算法所用时间： 分治算法所用时间 ：动态规划所用时间：
}
}
long = System.currentTimeMillis (); return sum ;
}//BF算法
public static int maxSum2(int left , int right ){
int sum =0;
if (left ==right ) sum =a [left ]>0?a [left ]:0; else { }
return sum ;
int center =(left +right )/2; int leftsum =maxSum2(left , center ); int rightsum =maxSum2(center +1,right ); int s1=0; int lefts =0;
for (int i =center ; i >=left ; i --){ }
int s2=0; int rights =0;
for (int i =center +1;i
sum =s1+s2;
if (sum
rights +=a [i ];
if (rights >s2) s2=rights ; lefts +=a [i ];
if (lefts >s1) s1=lefts ;
}//分治算法
public static int maxSum3(){
int n =a . length -1; int sum =0; int b =0;
for (int i =1;i
if (b >0)b +=a [i ]; else b =a [i ]; if (b >sum ) sum =b ;
}
}
return sum ; //动态规划
2. 结果截图
时间单位：ns
（1）10个数据
（2）50个数据
（3）100个数据
（4）500个数据
（5）1000个数据
（6）5000个数据
(7)10000个数据
（8）100000个数据
通过时间复杂度的分析和实验结果可以看出各算法的好坏依次是动态规划算法、分治算法，BF 算法，当数据较小时各算法之间的差距并不大，甚至有时BF 算法还优于分治，而且数据越大，BF 算法的缺点越明显，与动态规划的差距越大。
实验报告
课程名称 算法分析与设计 实验项目名称 最大字段和问题 班级与班级代码 实验室名称（或课室） 实验楼802 专 业： 计算机科学与技术 任课教师： 李绍华 学 号： 姓 名： 实验日期： 2016年11月25日
广东财经大学教务处 制
姓名 实验报告成绩
评语：
指导教师（签名） 年 月 日
说明：指导教师评分后，实验报告交院（系）办公室保存。
一、实验目的
(1)能够熟悉最大字段和问题这个算法
(2)分别使用三种不同算法：暴力算法、分治算法、动态规划算法，体会其算法思想并比较时间复杂度。
二、实验设备
硬件： P4 2.0G 1G内存60G 硬盘以上电脑 软件： C 、C++编程环境，Java 编程环境，windows7
三、问题与算法描述
1、问题描述
给定由n 个整数（可能为负整数）组成的序列a1、a2、……a n ，求该序列形如∑a k 的字段和的最大值。当所有整数均为负整数时定义其最大字
k =i j
段和为0。依次定义，所求的最优值为max{0，2、算法描述 BF 算法
1
a k }。 max ∑k =i
j
对于起点 i，遍历所有长度为1,2, …,n-i+1的子区间和，遍历所有的字 段，找出最大字段和。 分治算法
求子区间及最大和，从结构上是非常适合分治法的，因为所有子区间 [start, end]只可能有以下三种可能性: 1.在[1, n/2]这个区域内 2. 在[n/2+1, n]这个区域内
3. 起点位于[1,n/2],终点位于[n/2+1,n]内
以上三种情形的最大者，即为所求. 前两种情形符合子问题递归特性，所 以递归可以求出. 对于第三种情形，则必然包括了n/2和n/2+1两个位置， 这样就可以利用第二种穷举的思路分别向左右扩张求出。 动态规划
扩展到二维空间令b[j]表示以位置 j 为终点的所有子区间中和最大的一 个子问题:如j 为终点的最大子区间包含了位置j-1, 则以j-1为终点的最 大子区间必然包括在其中，如果b[j-1] >0, 那么显然b[j] = b[j-1] + a[j]，用之前最大的一个加上a[j]即可，因为a[j]必须包含；如果 b[j-1]
3、算法时间复杂性分析
BF 算法：经过两次嵌套循环时间复杂度：O(n2)
分治算法：每递归一次需logn ，全部需要n 次运算量，时间复杂度：O(nlogn)动态规划算法：只经历了一次循环，时间复杂度：O(n)
四、实验调试过程中出现的问题
实验过程中，主要遇到了两个问题，随机函数和时间计算函数不知如何进行，虽然之前在以前的课程中学习过，但是由于时间长已经忘记，通过查阅和同学帮助最终解决。 五、实验结果
1. 源代码
package 算法实验2;
import java.util.Random;
public class Maxfield { static int a [] =new int [1001];
public static void main(String[] args ) { // TODO Auto-generated method stub Random ran =new Random(); for (int i =1;i
System. out .print("" );
}
long starttime = System.nanoTime (); int sum1= maxSum1();
long endtime = System.nanoTime (); long starttime1 = System.nanoTime (); int sum2=maxSum2(1,a . length -1); long endtime1 = System.nanoTime (); long starttime2 = System.nanoTime (); int sum3=maxSum3();
long endtime2 = System.nanoTime ();
System. out .println(" BF算法所求最大字段和为： "+sum1+" BF" +(endtime -starttime )); System. out .println(" 分治算法所求最大字段和为 ：" +sum2+" " +(endtime1-starttime1)); System. out .println(" 动态规划所求最大字段和为： "+sum3+" " +(endtime2-starttime2));
}
public static int maxSum1(){ long = System.currentTimeMillis (); int n =a . length -1; int sum =0;
int =0;int =0; for (int i =1;i
for (int j =i ; j sum ){ sum =thissum ; besti =i ;
bestj = j ;
算法所用时间： 分治算法所用时间 ：动态规划所用时间：
}
}
long = System.currentTimeMillis (); return sum ;
}//BF算法
public static int maxSum2(int left , int right ){
int sum =0;
if (left ==right ) sum =a [left ]>0?a [left ]:0; else { }
return sum ;
int center =(left +right )/2; int leftsum =maxSum2(left , center ); int rightsum =maxSum2(center +1,right ); int s1=0; int lefts =0;
for (int i =center ; i >=left ; i --){ }
int s2=0; int rights =0;
for (int i =center +1;i
sum =s1+s2;
if (sum
rights +=a [i ];
if (rights >s2) s2=rights ; lefts +=a [i ];
if (lefts >s1) s1=lefts ;
}//分治算法
public static int maxSum3(){
int n =a . length -1; int sum =0; int b =0;
for (int i =1;i
if (b >0)b +=a [i ]; else b =a [i ]; if (b >sum ) sum =b ;
}
}
return sum ; //动态规划
2. 结果截图
时间单位：ns
（1）10个数据
（2）50个数据
（3）100个数据
（4）500个数据
（5）1000个数据
（6）5000个数据
(7)10000个数据
（8）100000个数据
通过时间复杂度的分析和实验结果可以看出各算法的好坏依次是动态规划算法、分治算法，BF 算法，当数据较小时各算法之间的差距并不大，甚至有时BF 算法还优于分治，而且数据越大，BF 算法的缺点越明显，与动态规划的差距越大。