用动态规划算法求解最大子段和.doc

《算法设计与分析》课程实验报告（一） 实验题目 用动态规划算法求解最大子段和 实验时间 一、实验目的及要求 1. 理解动态规划算法的概念 2. 掌握动态规划算法的基本要素：（1）最优子结构性质 （2）重叠子问题性质 3. 掌握设计动态规划算法的步骤 （1）找出最优解的性质，并刻画其结构特征 （2）递归地定义最优值 （3）以自底向上的方式计算最优值 （4）根据计算最优值时得到的信息构造最优解 5.通过一些范例学习动态规划算法设计策略 二、实验内容、过程和结果（实验主要内容的介绍、主要的操作步骤、程序代码和测试数据及实验结果） 1.实验内容介绍： 求解最大子段和问题：给定由n个整数（可能为负数）组成的序列a1,a2,...,an,求该序列形如的子段和的最大值.当所有整数均为负整数时定义其最大子段和为0. 依次定义,所求的最优值为 ｛0,｝ 。用分治法求解最大子段和步骤:首先将所给的序列a[1:n]分为长度相等的两段 a[1:n/2]和a[n/2+1:n],然后分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种情形： 1 a[1:n]的最大子段和与a[1:n/2]的最大子段和相同 2 a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同 3 a[1:n]的最大子段和为，且1≤i≤n/2, n/2+1≤j≤n 2.程序代码： #include int MaxSubSum int a[10], int left,int right int i 0; int sum 0; if left right sum a[left] 0 ? a[left]:0 ; else int center left+right /2 ; int leftsum MaxSubSum a, left, center ; int rightsum MaxSubSum a, center+1,right ; int s1 0; int lefts 0; for i center;i left;i-- lefts+ a[i]; if lefts s1 s1 lefts; int s2 0; int rights 0; for i center+1;i right;i++ rights+ a[i]; if rights s2 s2 rights; sum s1+s2; if sum leftsum sum leftsum; if sum rightsum sum rightsum; return sum; int main int a[10] 1,5,3,7,8,10,-5,6,7,-10 ; int b 0; b MaxSubSum a,0,9 ; printf %d,b ; 测试数据及实验结果 将以上代码进行调试，运行，所得结果正确. 2