求子数组的最大和问题--一道浙江大学考研压轴题(被Google拿来做面试题)

一 问题：

输入一组数据，有正数和负数,数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

二 解题思路：

本题不能采用枚举法，因为题目要求时间复杂度为O(n)。现在先举一个例子

有一组数据，共12个，它们是：-2 3 -1 3 -6 7 8 -1 10 -20 -11 18

通过手算和观察，最大和是24，这个子数组是:7 8 -1 10

我们现在设三个变量max sum a[i],max表示子数组最大和,sum表示子数组当前和,a[i]表示当前正在处理的数

sum=sum+a[i], if(sum<=0) sun=0, if(sum>max) max=sum

max=0 sum=0 a[i]=--2

0 -2/0 3 ----------此时累加和sum是-2，要清零

3 3 -1 ----------此时sum>max,要改变max为sum的值

3 2 3 ----------以下依次类推

5 5 -6

5 -1/0 7

7 7 8

15 15 -1

15 14 10

24 24 -20

24 4 -11

24 -7/0 18

24 18

三 代码

/*This is a free Program, You can modify or redistribute it under the terms of GNU*Description:求子数组的最大和*Language: C++*Development Environment: VC6.0*Author: Wangzhicheng*E-mail: 2363702560@qq.com*Date: 2012/11/17*//*输入一组数据，有正数和负数,数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。*/#include <iostream>#include <cstdlib>#include <vector>#include <algorithm>using namespace std;template<class Type>class SubArray {private:vector<Type>v;       //存放一组数据int N;               //这组数据的个数Type max;public:SubArray(int n) {if(n<=0) {cerr<<"输入数据的个数必须大于0!"<<endl;exit(1);}N=n;int i;Type e;for(i=0;i<n;i++) {cout<<"请输入第"<<i<<"个数据:";cin>>e;if(!cin.good()) {cerr<<"输入数据格式错误!"<<endl;return;}v.push_back(e);}max=0;}void show() const {copy(v.begin(),v.end(),ostream_iterator<Type>(cout," "));cout<<endl;cout<<"子数组最大和是:"<<max<<endl;}void Solution() {Type sum=0;int i;for(i=0;i<v.size();i++) {sum+=v[i];if(sum<=0) sum=0;else if(sum>max) {max=sum;}}}};void main() {SubArray<int>a(8);a.Solution();a.show();}

四： 测试

输入8个数据：1 -2 3 10 -4 7 2 -5

屏幕输出：