欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

最大子序列跟算法分析

程序员文章站 2022-05-03 20:32:26
...
最大子序列和算法分析

问题描述:给定n个整数序列{a1,a2,...,an},求函数f(i,j)=max{0,Σak}(k:连续的从i取到j);

问题即为求已连续子列和的最大值,若果最大值为负数则取0,比如8个数序列{-1,2,-3,4,-2,5,-8,3},那摩最大子序列和为4+(-2)+5=7.

这个问题有四种不同复杂度的算法,算法1到四的时间复杂度是O(n3),O(n2),O(nlogn),O(n);

算法一

最直接的方法是穷举法,列出所有的情况,我们可以设定子序列的左端i和右端j,再利用一层计算出a[i]到a[j]的和.

//最大子列和穷举法
#include
using namespace std;
int Find_Maxsun(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_Maxsun(int*a, int n){
int MaxSun = 0, i, j, k;
int NowSum;
for (i = 0; i for (j = 0; j NowSum = 0;
for (k = i; k NowSum += a[k]; /*从a[i]到a[j]的子序列*/
if (NowSum>MaxSun)
MaxSun = NowSum; /*更新结果*/
}
return MaxSun;
}

很显然,暴力法使用啦3重for循环,算法时间复杂度为O(n3),这当然也是一个最笨的算法,但数据难非常庞大时候,哪怕是要算到死的节奏,我们可以清楚看到第三层for循环,

j每加一次,子列和都要重头算一次,那我们为何不去利用j-1的结果呢?也就是说我们将j-1的结果保存下来,在计算j步的结果时候,只需要在j-1步的基础上再加上a[j],就可以啦,于是有啦算法二。

算法二:

#include
using namespace std;
int Find_Maxsun2(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_Maxsun2(int*a, int n){
int i, j, NewSum = 0, MaxSum= 0;
for (i = 0; i NewSum = 0;
for (j = i; j NewSum += a[j]; /*每一次在j-1条件下更新NewSum*/
if (NewSum>MaxSum) /*更新MaxSum*/
MaxSum = NewSum;
}
}
return MaxSum;
}

这个算法比1聪明,算法复杂度是O(n2),显然还不是我们想要的复杂度。

算法三:

算法三使用的是分治法的思想,基本思想不言而喻先分后治,将问题分解为小问题然后在可以总和小问题来解决,我们把原序列一分为二,那么最大子序列在左边,在右边,或者跨越边界,基本思路如下:

第一步:将原序列一分为二,分成左序列和右序列。

第二步:递归求出子序列S左和S右。

第三部:从中分线向两边扫描,找出跨越中线的最大子序列和S中。

第四步:求得S=max{S左,S中,S右};

代码实现如下:

#include
using namespace std;
int Find_MaxSum3(int*a,int low,int high);
int Max(int a,int b,int c);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_MaxSum3(int*a,int low,int high){
int MaxSum = 0, MidSum, LeftSum, RightSum,i;
MidSum = 0;
if (low == high){ /*递归的终止条件*/
if (a[low] > 0)
return a[low];
else
return 0;
}
int mid = (low + high) / 2; //找到分的中点
LeftSum = Find_MaxSum3(a, low, mid); /*递归找到左边序列最大和*/
RightSum = Find_MaxSum3(a, mid + 1, high); /*递归找到右边序列最大子序列和*/
/*然后可以求中间跨越边界序列的最大和*/
int NewLeft = 0,Max_BorderLeft=0, NewRight = 0,Max_BorderRight=0;
for (i = mid; i >= low; i--){ /*向左扫描找到最大和*/
NewLeft += a[i];
if (NewLeft > Max_BorderLeft)
Max_BorderLeft = NewLeft;
}
for (i = mid + 1; i NewRight+=a[i];
if (NewRight >= Max_BorderRight)
Max_BorderRight = NewRight;
}
MidSum = Max_BorderRight + Max_BorderLeft;
return Max(LeftSum, MidSum, RightSum); /*返回治的结果*/
}
int Max(int a, int b, int c){ /*找出3者中最大的数*/
if ( a>= b&&a >= c)
return a;
if (b >= a&&b >= c)
return b;
if (c >= b&&c>=a)
return c;
}

我们来算一算这个算法时间复杂度:

T(1)=1;

T(n)=2T(n/2)+O(n);

=2kT(n/2k)+kO(n)=2kT(1)+kO(n)(其中n=2k)=n+nlogn=O(nlogn);

虽然这个算法已经非常好啦,但是并不是最快的算法。

算法四:

算法四叫做在线处理。意思为,每读入一个数据就进行及时处理,得到的结果是对于当前读入的数据都成立,即为在任何位置终止读入,算法都可以给出正确的解,边读边解。

#include
using namespace std;
int Find_MaxSum4(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_MaxSum4(int*a, int n){
int i, NewSum = 0, MaxSum = 0;
for (i = 0; i NewSum += a[i]; /*当前子序列和*/
if (MaxSum MaxSum = NewSum; /*更新最大子序列和*/
if (NewSum NewSum = 0;
}
return MaxSum;
}

这种算法是将读入的数据一个个扫描一遍,只有一个for循环,解决同一个问题算法差别大,在于一个窍门,让计算机记住一些关键的中间结果,避免重复计算。

最大子序列跟算法分析

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。

相关文章

相关视频