网站运营与管理的心得体会,网站用户管理体系,wordpress 页面改造,wordpress 发送邮件插件一、问题描述给定由n个整数组成的序列(a_1,a_2,…,a_n)#xff0c;最大子段和问题要求该序列形如 的最大值(1≤i≤j≤n)#xff0c;当序列中所有整数均为负整数时#xff0c;其最大子段和为0。例如#xff0c;序列(-20, 11, -4, 13, -5, -2)的最大子段和为#xff1a; 注意…一、问题描述给定由n个整数组成的序列(a_1,a_2,…,a_n)最大子段和问题要求该序列形如 的最大值(1≤i≤j≤n)当序列中所有整数均为负整数时其最大子段和为0。例如序列(-20, 11, -4, 13, -5, -2)的最大子段和为 注意必须是连续整数的和。二、分治策略1划分–按照平衡子问题的原则将序列( , ,…, ) 划分成长度相同的两个子序列( ,…, )和( ,…, )则会出现以下三种情况 ① , ,…, 的最大子段和 ,…, 的最大子段和② , ,…, 的最大子段和 ,…, 的最大子段和③ , ,…, 的最大子段和 , 且1≤i≤⌊ ⌋ , ⌊ ⌋1≤j≤n2求解子问题对于划分阶段的情况①和②可递归求解对情况③分别计算则 为情况③的最大子段和。3合并–比较在划分阶段的三种情况下的最大子段和取三者之中的较大者为原问题的解。步骤示意图三、算法实现 int MaxSum(int a[ ], int left, int right){sum0;if (left right) { //如果序列长度为1直接求解if (a[left]0) suma[left];else sum0;}else {center(leftright)/2; //划分leftsumMaxSum(a, left, center); //对应情况①递归求解rightsumMaxSum(a, center1, right); //对应情况②递归求解s10; lefts0; //以下对应情况③先求解s1for (icenter; ileft; i--) {leftsa[i];if (leftss1) s1lefts;}s20; rights0; //再求解s2for (jcenter1; jright; j) { rightsa[j];if (rightss2) s2rights;}sums1s2; //计算情况③的最大子段和 if (sumleftsum) sumleftsum; //合并在sum、leftsum和rightsum中取较大者if (sumrightsum) sumrightsum;}return sum;
}
思考采用分治法求解(-20,11,-4,13,-5,-2)的最大子段和, 写出求解过程。四、时间复杂度分析对应划分得到的情况①和②需要分别递归求解对应情况③两个并列for循环的时间复杂性是O(n)所以存在如下递推式综上时间复杂性为O(nlog2n)。内容有待完善请客官等待更新
