求最大子段和问题讲解.doc

算法设计与分析实验报告 学院：信息工程与自动化学院 专业：软件工程141 姓名：赵凛威 学号：201410413111 昆明理工大学信息工程与自动化学院学生实验报告 （ 2015 —2016 学年 第 1 学期 ） 课程名称：算法设计与分析 开课实验室：信自楼445 2016 年5月 27日和6月3日 年级、专业、班 软工141 学号 201410413111 姓名 赵凛威 成绩 实验项目名称 最大子段和问题 指导教师 吴霖 教师评语 该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强 □ B.中等 □ C.差 □ 该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般 □ C.没有 □ 教师签名： 年 月 日 一、上机目的及内容 1.上机内容 给定有n个整数（可能有负整数）组成的序列（a1,a2,…,an），求改序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 利用蛮力法求解： int maxSum(int a[],int n) { int maxSum = 0; int sum = 0; for(int i = 0; i n; i++) //从第一个数开始算起 { for(int j = i + 1; j n; j++)//从i的第二个数开始算起 { sum = a[i]; a[i] += a[j]; if(a[i] sum) { sum = a[i]; //每一趟的最大值 } } if(sum maxSum) { maxSum = sum; } } return maxSum; } 利用分治法求解： int maxSum(int a[],int left, int right) { int sum = 0; if(left == right) //如果序列长度为1，直接求解 { if(a[left] 0) sum = a[left]; else sum = 0; } else { int center = (left + right) / 2; //划分 int leftsum = maxSum(a,left,center); //对应情况1，递归求解 int rightsum = maxSum(a, center + 1, right);//对应情况2， 递归求解 int s1 = 0; int lefts = 0; for(int i = center; i = left; i--) //求解s1 { lefts += a[i]; if(lefts s1) s1 = lefts; //左边最大值放在s1 } int s2 = 0; int rights = 0;