最大子段和问题改

最大子段和问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 改 计算机算法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 与 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 最大子段和问题 学号:E15301117 E15301098 E15301111 E15301107 姓名:张静 周罕张健夏国峰 日期:2015.10.26 目录 最大子段和问题的简单和改进算法分 析.................................................................... 3 最大子段和问题的简单思 想:............................................................................. 3 算法分析如 下:............................................................................................... ...... 3 1 时间复杂度分 析:................................................................................................. 4 最大子段和问题的分治算法分 析................................................................................ 5 最大子段和问题的分治算法的基本思 想:......................................................... 5 算法分析如 下:..................................................................................................... 5 时间复杂度分 析:................................................................................................. 6 最大子段和问题的动态 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 算 法................................................................................ 7 动态规划的基本思 路:......................................................................................... 7 算法的时间复杂度分 析:..................................................................................... 8 最大子段和问题的简单和改进算法分析 作者:张静 2 学号:E15301117 最大子段和问题的简单思想: 1、给定有n个整数(可能是负整数)，组成的序列a1，a2，……，an 2、计算该序列形如?ak的字段和的最大值 k=ij 3、当所有整数均为负数是定义其最大子段和位0;以此定义，所求的最优值为max{0，max1?i?j?nak}?ki=j 算法分析如下: //最大子段和问题的简单算法 public static void Max_Sum1(intn,int[] a){ int sum=0; intbesti=0,bestj=0; for(int i=0;ifor(int j=i;jintthissum=0; //穷举子段[i,j],求该区间所有数的和 for(int k=i;kif(thissum>sum){ sum=thissum; besti=i; bestj=j; } } } 3 //打印最大子段的和，子段的首尾坐标 System.out.println(sum); System.out.println(besti); System.out.println(bestj); } //最大子段和问题的简单算法的改进 public static void Max_Sum2(intn,int[] a){ int sum=0; intbesti=0,bestj=0; for(int i=0;i } for(int j=i;jsum){ sum=thissum; besti=i; bestj=j; } } } System.out.println(sum); System.out.println(besti); System.out.println(bestj); 时间复杂度分析: 对于第一个简单算法用到了三个for循环，可以看出他需 要的时间复杂度为也就是?(n3),中间用到一个if语句的交 换，时间复杂度为?(1),所以该算法 3的时间复杂度为T(n)=?(n)。 对于第二个改进算法，注意到了?ak=aj+ k=ijak，则可以将第一个算?ki=j-1 法的最后一个for循环省去，避免重复，所以改进之后的 时间复杂度为T(n)=?(n2)。 4 最大子段和问题的分治算法分析 作者:周罕 学号:E15301098 最大子段和问题的分治算法的基本思想: 将所给序列a[1:n]分成长度相等的两段，分别为a[1:2/n]和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]的最大子段和为ai+...+aj ,其中1 在以上三种情况中，1和2比较简单，可用递归方法求出，在第三种情况中，先求出a[1:n]的最大子段和s1,同时求出a[n/2+1:n]的最大子段和s2，则s1+s2就是第三种情况的最优解。 算法分析如下: IntMaxSubSum(int *a,intleft,int right) { 5 Int sum=0;//将最大子段和sum的初始值赋为0 If(left==right) sum=a[left]>0?a[left]:0 //如果序列a中只有一个元素，若此元素是正数，则将其赋值给sum,若此元素为负数，则sum=0; Else{ Int center=(left+_right)/2; //取序列a的中间元素; Intleftsum=MaxSubSum(a,left,center); Intleftsum=MaxSubSum(a,left,center); //分别递归求出左右两部分的最大子段和; //以上代码为三种情况中的第一和第二种情况; Int s1=0;//在第三种情况下，将左半部分的最大子段和s1赋值为0 Int lefts=0;//取中间变量left For (int i=center;i>=left:i--) {lefts+=a[i]; If(lefts>s1) s1=lefts; }//从序列中的a[center]开始，将初值赋为lefts=a[center], 此时比较lefts与s1的大小，若lefts>s1 ,则s1=lefts;循坏继续，lefts+=a[i]，每循环一次，比较s1与lefts的大小，将较大的值赋值给s1,求出左半部分的最优解; Int s2=0; Int rights=0; 6 For (int i=center+1;i{rights+=a[i]; If(rights>s2) s2=rights;/从序列中的a[center+1]开始，将初值赋为 rights=a[center+1],此时比较rights与s2的大小，若rights>s2 ,则s2=rights;循坏继续，rights+=a[i]，每循环一次，比较s2与rights的大小，将较大的值赋值给s2,求出右半部分的最优解; Sum=s1+s2; If(sumIf(sum} //取三种情况中的最大值，即为序列a的最大子段和; Return sum; } IntMaxSum(intn,int *a) { Return MaxSubSum(a,1,n); } 时间复杂度分析: 对于前两种情况，需要分别递归求解，对于第三种情况，两个并列的for循环的时间浮渣度是O(n),所以时间复杂度 7 的递推公式如下: T(n)=O(1); T(n)=2T(n/2)+O(n); 所以，该算法的时间复杂度为T(n)=O(nlogn)。 最大子段和问题的动态规划算法 作者:E15301111 张健 E15301107 夏国峰 动态规划的基本思路: 现声明一个记号b[j]=max{a[i]++a[j]}，其中1?i由此定义可知如果b[j-1]0时，那么b[j]=b[j-1]+a[j]; 也就是说有下面的动态规划递归公式成立: b[j]=max{ b[j-1]+a[j], a[j]} ，1?j?n; 下面举个例子来说明上述算法: 设一个数组a[1..6]={-2，3，5，-4，-2，1} 由上述定义知: b[1]=max{a[1]}=-2 b[2]=max{b[1]+a[2],a[2]}=3 b[3]=max{b[2]+a[3],a[3]}=8 b[4]=max{b[3]+a[4],a[4]}=4 b[5]=max{b[4]+a[5],a[5]}=2 b[6]=max{b[5]+a[6],a[6]}=3 8 最后，根据b[j]的定义，取这6个数当中最大的值作为b[j]的值，也就是我们要求的最大字段和。 由此可以得出求解最大字段和的动态规划算法如下: intMaxsum(intn,int *a){ //n代表的是数组中元素的个数，a代表的是目标数组的数组名,此处的b就相当于前面所说的b[j],通过不断的与sum作比较找出最大的b[j],并赋值给sum。 intsum=0,b=0; for(int i=1;iif(b>0) b=b+a[i]; //b是用来存储每次累加的计算结果。 //第一次循环实际上是将a[1]的值赋值给b，执行else语句。 else b=a[i]; if(b>sum) //每次的累加结果都会与目前最大的累加和作比较，如果本次的累加和比先前得到的最大累加和大，那么就改变这个最大累加和的值。 sum=b; } return sum; //返回最大字段和。 } 备注:经过我与夏国锋同学的讨论发现该程序也存在些许 9 的漏洞，那就是这里sum一开始就给了0这个数字，那么考虑一种极端的情况就是当所有的b都是小于0的话，显然最后返回的sum就是0 ，然而在这种情况最大字段和显然应该是个负数。 算法的时间复杂度分析: 该算法的问题规模是n基本操作则位于for循环体中for循环要执行的次数则固定为n;故该算法的时间复杂度为O(n)。 百度搜索“就爱阅读”,专业 资料 新概念英语资料下载李居明饿命改运学pdf成本会计期末资料社会工作导论资料工程结算所需资料清单 ,生活学习,尽在就爱阅读网92to.com,您的在线图书馆 10