算法.最大段和.doc

《算法.最大段和.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、〖题目描述〗 在一个一维数组里找出连续的几个数,使数的总和最大。  计算最大子段和的5种算法（c实现） #include#define sum 21int b[sum];算法1int MAX_SUM(int a[]){int max,i,j,k,k1;                          k1=0;for(i=0;i<=5;i++)                                      //进行3重循环，计算出所有可能的子段和{for(j=i;j<=5;j++){         for( k=i;k

2、<=j;k++)   {    b[k1]+=a[k];   }   if(b[k1]<0)            b[k1]=0;   k1++;}}max=b[0];for(k1=1;k1

3、j<=5;j++){   if(i==j)    b[k]=a[j];   else    b[k]=b[k-1]+a[j];          //利用前k-1个已计算出的最大子段和求k个的最大子段和   if(b[k]<0)    b[k]=0;   k++;}    max=b[0];for(k=1;k

4、 int leftsum,rightsum,center,s1,s2,lefts,rights,s;if (left==right)                                               //当left==right时，直接计算最大子段和    {if (a[left]>0) return a[left];     else return 0;}else{    center=(left+right)/2;    leftsum=MAX_SUM(a,left,center);                   //否则

5、计算当前子段[1..n/2]的最大子段rightsum=MAX_SUM(a,center+1,right);      //否则计算当前子段[n/2+1..n]的最大子段}s1=0;lefts=0;for(int i=center;i>=left;i--)                               //计算前半段子段和{     lefts+=a[i];if(lefts>s1)                                                   //如果子段和小于0，记为0    s1=lefts;}s2=r

6、ights=0;for(int j=center+1;j<=right;j++)                     //计算后半段子段和{   rights+=a[j];if(rights>s2)   s2=rights;}s=s1+s2;                                                    //计算跨越2子段的子段和s if(s>leftsum)       //前半段leftsum，后半段rightsum，和s的大小，最大者即是                            当前段的最大子段

7、和{if(s>rightsum)return s;elsereturn rightsum;}else{if(leftsum>rights)return leftsum;elsereturn rightsum;}}算法4int MAX_SUM(int a[])                                    //根据推导b[j]等于a[0..j]的最大子段和{int temp,max;                                   int b[6];                                  

8、                  //辅助数组b，