1 #include<stdio.h> 2 typedef struct addelem{ 3     int low; 4     int high; 5     int max; 6 }add; 7  8 add fun1(int *A,int length){             //线性时间复杂度：T（n）=O（n）;最优法 9     add ad;10     int i,sum;11     sum=A[0];ad.low=0;ad.high=0;ad.max=A[0];12     //length=sizeof(A)/sizeof(int); 13     //此处的length值为1；算的应该是A这个地址的长度。14     for(i=0;i<length;i++){15         if(sum>0)                //sum[i]=max(sum[i-1]+a[i],a[i])16             sum=sum+A[i];17         else{18             sum=A[i];19             if(sum>ad.max)ad.low=i;20         }21         if(sum>ad.max){22             ad.max=sum;            23             ad.high=i;        24         }25     }26     return ad;27 }28 29 add fun2(int *A,int length){        //暴力求解，时间复杂度T ( n ) = O ( n^2 ) ;不可取30     add ad;31     int i,j,sum;32     sum=A[0];ad.low=0;ad.high=0;ad.max=A[0];33     for(i=0;i<length;i++){34         for(j=i;j<length;j++){35             sum=sum+A[j];36             if(sum>ad.max){37                 ad.max=sum;38                 ad.low=i;39                 ad.high=j;40             }41         }42         sum=0;43     }44     return ad;45 }46 47 add bodymax(int *A,int low,int high){48     add ad;49     int i,mid,Lmax,Rmax,sum;50     ad.low=low;ad.high =high;51     mid=(low+high)/2;52     sum=0;Lmax=A[mid];Rmax=A[mid+1];53     for(i=mid;i>=0;i--){                        //从中间分别向两边求最大值54         sum=sum+A[i];55         if(sum>=Lmax){Lmax=sum;ad.low=i;}56     }57     sum=0;58     for(i=mid+1;i<(high-low+1);i++){59         sum=sum+A[i];60         if(sum>=Rmax){Rmax=sum;ad.high=i;}61     }62     ad.max=Lmax+Rmax;63     return ad;64 }65 add fun3(int *A,int low,int high){       //分治，归并求解T(n)=O(nlogn),不建议采用66     add Lad,Rad,Bodyad,ad;67     int mid=(low+high)/2;68     if(low==high){                                  //只有一个元素时69         ad.low=low;70         ad.high=high;71         ad.max=A[low];72         return ad;73     }74     else{75         Lad=fun3(A,low,mid);                   //左分76         Rad=fun3(A,mid+1,high);            //右分77         Bodyad=bodymax(A,low,high);    //求解    //与归并排序神似78         if(Bodyad.max>Lad.max &&Bodyad.max >Rad.max)79         return Bodyad;80         else return Rad.max>Lad.max? Rad : Lad;81     }82 }83 84 void main(){85     int i;86     int A[]={10,-12,-8,10,3,111,-12,1,3,2,-8,-6,-5,-3,-9,-117,115,-13};87     int length=sizeof(A)/sizeof(int);88     //add ad=fun1(A,length);89     add ad=fun3(A,0,length-1);90     for(i=0;i<length;i++)printf("%d  ",A[i]);91     printf("\n\n最大子数组和为：%d\n\n从元素A[%d]\t到\tA[%d]\n\n",ad.max,ad.low,ad.high);92 }