C语言求向量和的两则问题解答分享

#include
#include

//两者的最大值
int max( int x, int y );
//三者的最大值
int max2( int x, int y, int z );
//最原始的算法，复杂度为T(n)=O(n*n)
int oringinal( int v[], int len );
//原始基础上变体版,复杂度为T(n)=O(n*n)
int oringinal_ex( int v[], int len );
//分治法,复杂度为T(n)=O(n*log(n))
/*
 *分治法的思想是：将原数组分成两部分，要求的最大值
 *要么在左边这部分里面，要么在右边这部分里面
 *要么就在左右相交的交界处
 */
int divAndCon( int v[], int low, int high );
//扫描法,复杂度为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  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));
 
}


//扫描法,复杂度为T(n)=O(n)
int scan(int v[], int len)
{
     int maxsofar = 0;
     int maxendinghere = 0;
     int i = 0;
     for( i =0; i 

#include
#include

//返回最接近0的数
int closeZero( int x, int y );
//最原始的算法，复杂度为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  abs(y) )
     {
       x = y;
     }
     return x;
}

 

//最原始的算法，复杂度为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