最大子序列和的接口函数（3）

  

   

    

     

    
    

     

      int MaxSubsequenceSum(const int A[],int N)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int thisSum=0,MaxSum=0,j;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	for(j=0;j<N;j++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		thisSum+=A[j];
     
    
   

    

     

    
    

     
		printf("thisSum %d..A[%d]=%d\n",thisSum,j,A[j]);			
     
    
   

    

     

    
    

     
		if(thisSum>MaxSum)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			MaxSum=thisSum;
     
    
   

    

     

    
    

     
			printf("MaxSum:%d\n",MaxSum);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else if(thisSum<0)
     
    
   

    

     

    
    

     

      			thisSum=0;	
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return MaxSum;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int number[]={1,-1,3,4};
     
    
   

    

     

    
    

     
	int maxsum=0;
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	printf("start ....\n");	
     
    
   

    

     

    
    

     

      	maxsum=MaxSubsequenceSum(number,4);
     
    
   

    

     

    
    

     
	printf("maxsum:%d\n",maxsum);	
     
    
   

    

     

    
    

     
	exit(0);
     
    
   

    

     

    
    

     

      }
     
    
  
 

运行得出结果

  

   

    

     

    
    

     

      start ....
     
    
   

    

     

    
    

     

      thisSum 1..A[0]=1
     
    
   

    

     

    
    

     

      MaxSum:1
     
    
   

    

     

    
    

     

      thisSum 0..A[1]=-1
     
    
   

    

     

    
    

     

      thisSum 3..A[2]=3
     
    
   

    

     

    
    

     

      MaxSum:3
     
    
   

    

     

    
    

     

      thisSum 7..A[3]=4
     
    
   

    

     

    
    

     

      MaxSum:7
     
    
   

    

     

    
    

     

      maxsum:7
     
    
  
 

此算法的优点，它只对数据进行一次扫描，一旦A[j]被读入并处理，它就不再需要被记忆。在于它可以被顺序读入，在主存中不必存储数组任何部分，在任何时刻，算法都能对它已经读入的数据给出子序列问题的正确答案。

文章来源: xintiaobao.blog.csdn.net，作者：心跳包，版权归原作者所有，如需转载，请联系作者。

原文链接：xintiaobao.blog.csdn.net/article/details/89485557