#include<stdio.h>#include<stdlib.h>//兩者的最大值int max( int x, int y );//三者的最大值int max2( int x, int y, int z );//最原始的算法，復(fù)雜度為T(n)=O(n*n)int oringinal( int v[], int len );//原始基礎(chǔ)上變體版,復(fù)雜度為T(n)=O(n*n)int oringinal_ex( int v[], int len );//分治法,復(fù)雜度為T(n)=O(n*log(n))/* *分治法的思想是：將原數(shù)組分成兩部分，要求的最大值 *要么在左邊這部分里面，要么在右邊這部分里面 *要么就在左右相交的交界處 */int divAndCon( int v[], int low, int high );//掃描法,復(fù)雜度為T(n)=O(n)int scan(int v[], int len);void main(){     int i = 0;     int v[] = {31,-41,59,26,-53,58,97,-93,-23,84};     int len = 0;     int result;     len = sizeof(v) / sizeof(int);     printf("oringinal datas:/n");     for( i = 0; i < len; i++ )     {       printf("%d/t",v[i]);     }     printf("/n");     //最原始的算法     result = oringinal(v,len);     printf("oringinal(v,len):%d/n",result);     //最原始變體的算法     result = oringinal_ex(v,len);     printf("oringinal_ex(v,len):%d/n",result);     //分治法     result = divAndCon(v,0,len-1);     printf("divAndCon(v,0,len):%d/n",result);     //掃描法     result = scan(v,len);     printf("scan(v,len):%d/n",result);}//兩者的最大值int max( int x, int y ){     if( x < y )     {        x = y;     }     return x;}//三者的最大值int max2( int x, int y, int z ){     if( x < y )     {       x = y;     }     if( x < z )     {       x = z;     }     return x;} //最原始的算法，復(fù)雜度為T(n)=O(n*n)int oringinal( int v[], int len ){     int maxsofar = 0;     int i;     int j;     int sum = 0;     //通過(guò)雙層循環(huán)逐步掃描，通過(guò)max( sum, maxsofar)獲得當(dāng)前最大值     for( i = 0; i < len; i++ )     {       sum = 0;       for( j = i; j < len; j++ )       {         sum += v[j];         maxsofar = max( sum, maxsofar );        }     }     return maxsofar;}//原始基礎(chǔ)上變體版,復(fù)雜度為T(n)=O(n*n)int oringinal_ex( int v[], int len ){     int i = 0;     int j = 0;     int sum = 0;     int maxsofar = 0;     int *cumarr = ( int * )malloc( len * sizeof(int) );      for( i = 0; i < len; i++ )    {       if( i == 0 )       {         cumarr[0] = v[i];       }       else       {         cumarr[i] = cumarr[i-1] + v[i];       }      }    for( i = 0; i < len; i++ )      for( j = i; j < len; j++ )      {        if( i == 0 )        {           sum = cumarr[i];         }         else        {           sum = cumarr[j] - cumarr[i-1];         }         maxsofar = max(maxsofar,sum);      }      return maxsofar;} //分治法,復(fù)雜度為T(n)=O(n*log(n))int divAndCon( int v[], int low, int high ){    int mid = 0;    int lmax = 0;    int rmax = 0;    int sum = 0;    int i = 0;    if( low > high )    {      return 0;    }    if( low == high )    {      return max(0,v[low]);    }    mid = ( low + high ) / 2;    lmax = sum = 0;    for( i = mid; i >= low; i-- )    {       sum += v[i];       lmax = max(lmax,sum);    }    rmax = sum = 0;    for( i = mid + 1; i <= high; i++ )    {      sum +=v[i];      rmax = max(rmax,sum);    }    return max2(lmax + rmax,divAndCon(v,low,mid),divAndCon(v,mid+1,high)); }//掃描法,復(fù)雜度為T(n)=O(n)int scan(int v[], int len){     int maxsofar = 0;     int maxendinghere = 0;     int i = 0;     for( i =0; i < len; i++ )     {       maxendinghere = max(maxendinghere + v[i],0);       maxsofar = max(maxsofar,maxendinghere);     }     return maxsofar;} 

#include<stdio.h>#include<math.h>//返回最接近0的數(shù)int closeZero( int x, int y );//最原始的算法，復(fù)雜度為T(n)=O(n*n)int oringinal( int v[], int len );void main(){     int i = 0;     int v[] = {31,-41,59,26,-53,58,97,-93,-23,84};     int len = 0;     int result;     len = sizeof(v) / sizeof(int);     printf("oringinal datas:/n");     for( i = 0; i < len; i++ )    {      printf("%d/t",v[i]);    }    printf("/n");    //最原始的算法    result = oringinal(v,len);    printf("oringinal(v,len):%d/n",result); }//返回最接近0的數(shù)int closeZero( int x, int y ){     if( abs(x) > abs(y) )     {       x = y;     }     return x;} //最原始的算法，復(fù)雜度為T(n)=O(n*n)int oringinal( int v[], int len ){     int sofar = v[0];     int i;     int j;     int sum = 0;     for( i = 0; i < len; i++ )     {       sum = 0;       for( j = i; j < len; j++ )       {         sum += v[j];         sofar = closeZero( sum, sofar );       }     }      return sofar;}