首页 > 代码库 > [编程之美] 2.14 求数组的子数组之和的最大值

[编程之美] 2.14 求数组的子数组之和的最大值

问题描述:给定一个包含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 <iostream>
#include <algorithm>
#include <limits>
#include <vector>
using namespace std;

int MaxSum(vector<int>::iterator beg, vector<int>::iterator end)
{
    if(end <= beg) {
        return 0;
    }

	if(beg + 1 == end) {
		return *beg;
	}

	vector<int>::difference_type len = end - beg;
	vector<int>::iterator mid = beg + len / 2;

	int left = MaxSum(beg, mid - 1);
	int right = MaxSum(mid, end);
	int sum1 = 0, maximum = numeric_limits<int>::min();

	for(vector<int>::iterator iter = mid - 1; iter != beg - 1; --iter) {

		sum1 += *iter;

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

	int sum2 = 0;
    maximum = numeric_limits<int>::min();
	for(vector<int>::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<int> 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<int>::iterator beg, vector<int>::iterator end)
{
    if(end <= beg) {
        return 0;
    }

    vector<int>::difference_type len = end - beg;
    vector<int> m, s;
    m.resize(len);
    s.resize(len);
    s[0] = *beg;
    m[0] = *beg;

    vector<int>::iterator m_iter = m.begin() + 1, s_iter = s.begin() + 1;
    for(vector<int>::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<int>::iterator beg, vector<int>::iterator end)
{
    if(end <= beg) {
        return 0;
    }

    int maximum = numeric_limits<int>::min();
    int cur = 0;

    for(vector<int>::iterator iter = beg; iter != end; ++iter) {

        if(cur >= 0) {
            cur += *iter; 
        }
        else {
            cur = *iter;
        }

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

    return maximum;
}
如果当前计算的子数组和>=0,就将当前遍历的数组成员加到里面;如果当前计算的子数组和<0,就从当前遍历的数组成员开始计算。


6 小结

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

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