学步园

最大子序列问题描述：

给定N个数（其中可能有负数），求解 最大的子序列和。

int maxsubsum1(const int A[] , int n)
{
	int thissum , max ,  k ;
	max = 0 ;
	for ( int i = 0 ; i < n;++i)
	   for(  int j = i ; j < n ;++j)
	       {
	       	 thissum = 0 ;
	       	 for ( k = i ; k <= j ;++k)
	       	      thissum  += A[k];
	       	 if ( thissum > max ) 
	       	     max = thissum ;
	       }
	return max;
}

</pre><pre name="code" class="cpp">

穷举所有可能，复杂度N的三次方。

<pre name="code" class="cpp">int maxsubsum2(const int A[], int n)
{
	int thissum  , max = 0 ; 
	for ( int i = 0 ; i < n ;++i)
	{ 
	       thissum = 0 ;
	
	  for ( int j = i ; j < n ; ++j)
	    {
	    	  thissum  += A[j] ;
	    	  
	    	  if ( thissum > max )
	    	       max = thissum ;
	    	  
	    }  
    }
	    return max ;
	    
}

算法复杂度 复杂度N的平方。

int maxsubsum3(const int A[], int n)
{
     int thissum , maxsum  ;
     thissum = maxsum = 0 ;

     int maxele = A[0];// 如果数组全为负数，maxele为最大值

     for ( int i = 0 ; i < n ; ++i)
      {
           thissum += A[i];

           if ( thissum > maxsum)
               maxsum = thissum;
		   else  if ( thissum < 0)
               thissum = 0 ;
            if (maxele < A[i])
            maxele = A[i];
     }
      return maxsum > maxele ? maxsum : maxele ;//比较最大和 和 最大值 ，
}

</pre><pre name="code" class="cpp">

分治递归。。。。好厉害

<pre name="code" class="cpp">static int maxsub(const int A[] , int l , int r)
{
	int maxlsum , maxrsum;
	int maxlbsum , maxrbsum ;
	int lbsum , rbsum ;
	int center ;
	int max ;
	if( l == r) 
	  if (A[l] > 0) return A[l];
	  else return 0;
	  
	center = (l+r)/2;
	maxlsum = maxsub(A,l,center);
	maxrsum = maxsub(A,center+1,r);
	
	maxlbsum=0; lbsum = 0;
	for ( int i = center ; i >= 0;--i)
	{
		  lbsum += A[i];
		  if (lbsum > maxlbsum)
		      maxlbsum = lbsum;
	}
	maxrbsum=0; rbsum = 0;
	for ( int i =center+1; i < r;++i)
	{
		rbsum += A[i];
		if ( rbsum > maxrbsum)
		    maxrbsum = rbsum;
	}
	max = maxlsum > maxrsum ? maxlsum : maxrsum;
	max = max > (maxlbsum + maxrbsum) ? max : (maxlbsum+maxrbsum);
	return max;
}

int maxsubsum4(const int A[] , int n)
{
	maxsub(A,0,n-1);
}