求子数组的最大和有关问题-一道浙江大学考研压轴题(被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
屏幕输出：