求最大子段和C.C++程序实现及其效率分析.doc

求最大子段和1)简单蛮力算法的程序实现及其效率分析，2)分治法求解的程序实现及其效率分析，包括效率分析过程的递归求解。3)动态规划法求解的程序实现及其效率分析。分析：给定n个整数（可能为负数）组成的序列a1,a2 ,an,求该序列如的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为,例如，当（a1,a2,a3,a4,a4,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为20。解答：1）简单蛮力算法的程序实现及其效率分析程序实现：#include #include #define N 7int aN = -2,11,-4,13,-5,-2,8;/用蛮力法求最大子段和 int ManLiFa(int *a,int n) int besti=-1; int bestj=-1; int sum = 0; for(int i = 1;i=n;i+) int thissum = 0; for (int j = i;jsum) sum = thissum; besti = i; bestj = j; printf(起点 = +besti); printf(终点 = +bestj); return sum; int main() printf(蛮力法 最大子段和: %dn,ManLiFa(a, N);return 0;效率分析：从这个算法的两个for循环可看出它的时间复杂度，T(n)=O(n2)。2）分治法求解的程序实现及其效率分析。思路：针对最大子段和这个具体问题本身的结构，我们还可以从算法设计的策略上对上述O(n2)计算时间算法进行更进一步的改进。从问题的解结构也可以看出，它适合于用分治法求解。如果将所给的序列a1:n分为长度相等的两段a1:n/2和an/2+1:n,分别求出这两段的最大子段和，则a1:n的最大子段和有三种情况：（1） a1:n的最大子段和与a1:n/2的最大子段和相同（2） a1:n的最大子段和与an/2+1:n的最大子段和相同（3） a1:n的最大子段和为a+aj，并且1=i=n/2，n/2+1=j=n。对于（1）和（2）两种情况可递归求得，但是对于情况（3），容易看出an/2，an/2+1在最大子段中。因此，我们可以在a1:n/2中计算出s1=max(an/2+an/2-1+a),0=i=n/2，并在an/2+1:n中计算出s2= max(an/2+1+an/2+2+a)，n/2+1=i=n。则s1+s2为出现情况（3）的最大子段和。程序实现：#include #include #include #define N 7int MaxSubSum(int *a, int left, int right); /分治法求最大子段和 int aN = -2,11,-4,13,-5,-2,8;int MaxSum(int *a, int n) /a是数组,n是数组大小 return MaxSubSum(a, 0, n-1); /分治法int MaxSubSum(int a,int left,int right) int i,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,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(sumc,由此递归方程可知，T(n)=O(nlogn)。3)动态规划算法来处理这个问题。思路：在对于上述分治算法的分析中我们注意到，若记 则所求的最大子段和为由bj的定义可易知，当bj-10时bj=bj-1+aj，否则bj=aj。故bj的动态规划递归式为: bj=max(bj-1+aj,aj)，1=j=n。程序实现：#include #include #include #define N 7int aN = -2,11,-4,13,-5,-2,8;int MaxSumDP(int *a, int n) int i,sum=0,b=0; for(i=1;i0)b+=ai; elseb=ai;if(bsum)sum=b; return sum; int main() printf(动态规划 最大子段和: %dn, MaxSumDP(a, N); return