求最大连续子段和 的 dp算法

问题描述：

     有n个数（以下都视为整数，浮点的也一样），每个数有正有负，现在要在n个数中选取相邻的一段，使其和最大，输出最大的和。

问题分析：

    对于这样的问题，我们可以直接用暴力，一个双重循环，虽说可以，但也没有更高明的方法？  我们再分析这个问题，如果我们知道了某个数前面一段数的和，我们就该考虑把这个数加入到前一段，还是重新开始一段。这个地方很重要，如果前一段的和小于0，我们重新建一段，反之加到前一段。这样我们就可以把n个数分成几段了，且每一段都求出了他们的和，然后再循环一次求出最大的一个和，我们就得到想要的结果了，也可以在分段的时候直接求结果。

代码

  

   

    

     

    
    

     

      int MaxSub (int a[])
     
    
   

    

     

    
    

     

      {  
     
    
   

    

     

    
    

     
    int dp[N], max, i;  
     
    
   

    

     

    
    

     

          max = dp[0] = a[0];  
     
    
   

    

     

    
    

     
    for (i=1; i<N; i++)  
     
    
   

    

     

    
    

     

          {  
     
    
   

    

     

    
    

     
        if (dp[i-1] > 0)  
     
    
   

    

     

    
    

     

                  dp[i] = dp[i-1] + a[i];  
     
    
   

    

     

    
    

     
        else  
     
    
   

    

     

    
    

     

                  dp[i] = a[i];  
     
    
   

    

     

    
    

     
        if (dp[i] > max)  
     
    
   

    

     

    
    

     

                  max = dp[i];  
     
    
   

    

     

    
    

     

          }  
     
    
   

    

     

    
    

     
    return max;  
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

原文链接：xindoo.blog.csdn.net/article/details/8872489