问题描述：给定一个包含N个整数的数组，求数组的子数组之和的最大值。

这是递归和贪心策略的一个经典问题。现在，对这个问题进行一下总结。

1 明确题意

题目中的子数组要求是连续的，也就是数组中的某个连续部分。

如果数组中都是正整数，直接相加就行。因此，主要是要考虑负数的情况。

2 直接求所有的子数组和

最简单且容易理解的解法是求出所有的子数组和，然后保存最大的和。

int MaxSum(int *A, int n)
{
    int maximum = -INF;
    int sum = 0;
    int i = 0, j = 0;

    for(i = 0; i < n; ++i) {

        sum = 0;

        for(j = i; j < n; ++j) {

            sum += A[j];

            if(sum > maximum) {
                maximum = sum;
            }
        }
    }

    return maximum;
}

3 递归

将数组分成长度相等的两部分：A[0]~A[n/2-1]和A[n/2]~A[n-1]。

那么对原数组而言，子数组和最大的子数组要么出现在A[0]~A[n/2-1]中，要么出现在A[n/2]~A[n-1]，要么子数组包含A[n/2-1]和A[n/2]并向左右延伸。

这就变成了递归：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int MaxSum(vector
      
       ::iterator beg, vector
       
        ::iterator end) { if(end <= beg) { return 0; } if(beg + 1 == end) { return *beg; } vector
        
         ::difference_type len = end - beg; vector
         
          ::iterator mid = beg + len / 2; int left = MaxSum(beg, mid - 1); int right = MaxSum(mid, end); int sum1 = 0, maximum = numeric_limits
          
           ::min(); for(vector
           
            ::iterator iter = mid - 1; iter != beg - 1; --iter) { sum1 += *iter; if(sum1 > maximum) { maximum = sum1; } } sum1 = maximum; int sum2 = 0; maximum = numeric_limits
            
             ::min(); for(vector
             
              ::iterator iter = mid; iter != end; ++iter) { sum2 += *iter; if(sum2 > maximum) { maximum = sum2; } } sum2 = maximum; return max(max(left, right), sum1 + sum2); } int main(int argc, char const *argv[]) { vector
              
                vec; vec.push_back(0); vec.push_back(-2); vec.push_back(3); vec.push_back(5); vec.push_back(-1); vec.push_back(2); cout << MaxSum(vec.begin(), vec.end()) << endl; return 0; } 
              
             
            
           
          
         
        
       
      
     
    
   
  

4 动态规划

假设已知A[0]~A[n-1]的子数组的和的最大值为m[n-1]，而以A[n-1]结束的子数组的和的最大值为s[n-1]，于是有：

（1）以A[n]为结束的子数组要么包含A[n-1]要么不包含A[n-1]，如果包含A[n-1]，那么以A[n]结束的子数组的和的值就是s[n - 1] + A[n]，如果不包含A[n - 1]，那么A[n]就是一个重新开始计算的地方，即当前只包含A[n]，于是有：s[n] = max(A[n], A[n] + s[n-1]);

（2）同样有，A[0]~A[n]的子数组要么以A[n]结束要么不以A[n]结束，如果以A[n]结束，子数组的和就是s[n]，如果不以A[n]结束，子数组的和就是m[n - 1]，于是有：m[n] = max(s[n], m[n - 1]);

根据上面的两个递推式就有：

int MaxSum(vector
  
   ::iterator beg, vector
   
    ::iterator end) { if(end <= beg) { return 0; } vector
    
     ::difference_type len = end - beg; vector
     
       m, s; m.resize(len); s.resize(len); s[0] = *beg; m[0] = *beg; vector
      
       ::iterator m_iter = m.begin() + 1, s_iter = s.begin() + 1; for(vector
       
        ::iterator iter = beg + 1; iter != end; ++iter) { *s_iter = max(*iter, *iter + *(s_iter - 1)); *m_iter = max(*s_iter, *(m_iter -1 )); ++m_iter; ++s_iter; } return m.back(); }
       
      
     
    
   
  

再来好好看看上面两个递推式：

s[n] = max(A[n], A[n] + s[n-1]);

m[n] = max(s[n], m[n - 1]);

从这两个递推式可以看出，如果已知s[n-1]、m[n-1]和A[n]就可以求得s[n]和m[n]，因此，事实上，只需要用两个变量来保存中间结果，而不需要用两个数组。

代码与上面的基本类似，就不再列出来了。

5 贪心

同时，从上面的两个递推式还可以看出，如果s[n-1] >= 0，就将A[n]放到当前考虑的子数组中，如果s[n-1] < 0，就从A[n]开始重新计算一个子数组。

这实际上使用的是贪心策略，不过贪心策略要经过严格的证明，这里还是可以从动态规划的方式来理解。于是有得到了史上最精简代码：

int MaxSum(vector
  
   ::iterator beg, vector
   
    ::iterator end) { if(end <= beg) { return 0; } int maximum = numeric_limits
    
     ::min(); int cur = 0; for(vector
     
      ::iterator iter = beg; iter != end; ++iter) { if(cur >= 0) { cur += *iter; } else { cur = *iter; } if(cur > maximum) { maximum = cur; } } return maximum; }
     
    
   
  

6 小结

本文给出了求子数组之和的最大值的四种方法，前面两种方法容易思考，代码略长且时间复杂度较高；后面两种方法不容易理解，但是代码简单且时间复杂度低。

其中的关键是先引出s[n]和m[n]，得到子数组之和的最大值的递推式，然后再通过递推式来简化算法。