最大子数组

一时失言乱红尘 2022-01-06 13:49 313阅读 0赞

/\*求子数组的最大和  
题目描述：  
输入一个整形数组，数组里有正数也有负数。  
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。  
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，  
因此输出为该子数组的和18。  
\*/

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 }

结果：

![111217070041918.png][]

转载于:https://www.cnblogs.com/zzsf/p/3837448.html

[111217070041918.png]: /images/20211227/456d7dff94fc41e796595bd8da8f8f35.png