题目大意：给出一序列，求该序列的子序列和最大的子序列。
下面共有四种算法：程序运行时间依次降低，最佩服的是最后的联机算法，时间已达到O(N).
注意C++中的函数调用与传值
-
下面分析四种算法：关于每种程序的运行时间，我们只关注他的最坏情况即可。
- 算法一，有三个大循环，假设第一个循环的大小N,每个循环都考虑最坏的情况，则总数为 O（N），
使用开销的思路推一下，精确分析可知，最大开销: ∑N−1i=0∑N−1j=i∑jk=i1,该和指出此程序三次循环被执行了多少次，由内到外求值，首先我们有
∑k=ij1=j−i+1
然后我们可以得到
∑j=iN−1(j−i+1)=(N−i+1)(N−i)2
继续：
∑i=0N−1(N−i+1)(N−i)2=∑i=1N(N−i+1)(N−i+2)2
=12∑i=1Ni2−(N+32)∑i=1Ni+12(N2+3N+2)∑i=1N1
=12N(N+1)(2N+1)6−(N+32N(N+1)2+N2+3N+22N)
=N3+3N2+2N6
所以算法一的最大消费为O（N3）。
- 算法一，有三个大循环，假设第一个循环的大小N,每个循环都考虑最坏的情况，则总数为 O（N），
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//最大子序列求和
//算法一
//穷举法
int maxsubsum(const vector &a)
{
int maxsum=0;
for(int i=0;i<a.size();i++)
for(int j=i;j<a.size();j++)
{
int ThisSum=0;
for(int k=i;k<=j;k++)
{
ThisSum+=a[k];
}
if(ThisSum>maxsum)
maxsum=ThisSum;
}
return maxsum;
}
//算法二
//对穷举法进行优化
int maxsubsum1(const vector &a)
{
int maxsum=0;
for(int i=0;i<a.size();i++)
{
int ThisSum=0;
for(int j=i;j<a.size();j++)
{
ThisSum+=a[j];
if(ThisSum>maxsum)
maxsum=ThisSum;
}
}
return maxsum;
}
//算法三
//分治法
int maxsumrec(const vector<int> &a,int left,int right)
{
if(left==right)
{
if(a[left]>0)
return a[left];
else
return 0;
}
int center=(left+right)/2;
int maxleftsum=maxsumrec(a,left,center);
int maxrightsum=maxsumrec(a,center+1,right);
int maxleftbordersum=0,leftbordersum=0;
int lrmax=max(maxleftsum,maxrightsum);
for(int i=center;i>=left;i--)
{
leftbordersum+=a[i];
if(leftbordersum>maxleftbordersum)
maxleftbordersum=leftbordersum;
}
int maxrightbordersum=0,rightbordersum=0;
for(int i=center+1;i<=right;i++)
{
rightbordersum+=a[i];
if(rightbordersum>maxrightbordersum)
maxrightbordersum=rightbordersum;
}
return max(lrmax,maxleftbordersum+maxrightbordersum);
}
int maxsubsum2(const vector <int> &a)
{
return maxsumrec(a,0,a.size()-1);
}
//算法四
//联机算法
int maxsubsum3(const vector<int >&a)
{
int MaxSum=0,ThisSum=0;
for(int j=0;j<a.size();j++)
{
ThisSum+=a[j];
if(ThisSum>MaxSum)
MaxSum=ThisSum;
if(ThisSum<0)
ThisSum=0;
}
return MaxSum;
}
int main()
{
int input[10];
for(int i=0;i<5;i++)
{
cin>>input[i];
}
//注意这里是去给vector容器初始化赋值的时候，区间是[begin,end];
vector<int>inputVetor(&input[0],&input[4]);
cout<<maxsubsum(inputVetor)<<endl;
cout<<maxsubsum1(inputVetor)<<endl;
cout<<maxsubsum2(inputVetor)<<endl;
cout<<maxsubsum3(inputVetor)<<endl;
return 0;
}
