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

《用动态规划算法求解最大子段和》由会员分享，可在线阅读，更多相关《用动态规划算法求解最大子段和（2页珍藏版）》请在装配图网上搜索。

1、算法设计与分析课程实验报告（一）实验题目用动态规划算法求解最大子段和实验时间一、实验目的及要求1. 理解动态规划算法的概念2. 掌握动态规划算法的基本要素：（1）最优子结构性质（2）重叠子问题性质3. 掌握设计动态规划算法的步骤（1）找出最优解的性质，并刻画其结构特征（2）递归地定义最优值（3）以自底向上的方式计算最优值（4）根据计算最优值时得到的信息构造最优解5.通过一些范例学习动态规划算法设计策略二、实验内容、过程和结果（实验主要内容的介绍、主要的操作步骤、程序代码和测试数据及实验结果）1. 实验内容介绍：求解最大子段和问题：给定由n个整数（可能为负数）组成的序列a1,a2,.,an,求该

2、序列形如兄气的 k =i子段和的最大值.当所有整数均为负整数时定义其最大子段和为0.依次定义，所求的最优值为max 0, max ak 。用分治法求解最大子段和步骤:首先将所给的序列a1:n 分为长度相等的两段 1i j n k=ia1:n/2和an/2+1:n,然后分别求出这两段的最大子段和，则a1:n的最大子段和有三种情形：（1）a1:n的最大子段和与a1:n/2的最大子段和相同（2）a1:n的最大子段和与an/2+1:n的最大子段和相同（3）a1:n的最大子段和为况 ak，且 1in/2, n/2+1jnk =i2. 程序代码：#include int MaxSubSum（int a10

3、, int left,int right） int i=0;int sum=0;if（left=right） sum=aleft0 ? aleft: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+=ai;if(leftss1)s1=lefts;int s2=0;int rights=0;for(i=center+1;is2)s2=rights;sum=s1+s2;if(sumleftsum) sum=leftsum;if(sumrightsum) sum=rightsum;return sum;:nt main()int a10 = 1,5,3,7,8,10,-5,6,7,-10;int b=0;b=MaxSubSum(a,0,9);printf(%d,b);3.测试数据及实验结果将以上代码进行调试，运行，所得结果正确.