相关描述:
连续子序列最大和,其实就是求一个序列中连续的子序列中元素和最大的那个。
比如例如给定序列:
{ -5,-2, 11, -4, 13, -5, -8 }
其最大连续子序列为{ 11, -4, 13 },最大和为20。
方法一:暴力 O(n^3)
算法描述:
暴力搞来就是枚举子序列的起点和终点,然后计算这一段的和,再通过不断地更新最大值即可。但是效率太低了。
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=100000; int a[maxn]; int main() { int n,max; while(scanf("%d",&n)&&n!=0) { for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } max=-1111111; for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { int sum=0; for(int k=i;k<=j;k++) { sum+=a[k]; } if(max<sum) max=sum; } } printf("%d\n",max); } return 0; }方法二:优化方法一,预处理O(n^2),其实就是在最开始时加一个数组sum[i]表示前i项的和,效率也不高。
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=100000; int a[maxn],sum[maxn]; int main() { int n,max; while(scanf("%d",&n)&&n!=0) { a[0]=0; sum[0]=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } max=-1111111; for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { int s=0; s=sum[j]-sum[i-1]; if(max<s) max=s; } } printf("%d\n",max); } return 0; }方法三:累计遍历算法O(n),效率很高了。
遍历序列的时候对Sum进行累计,如果Sum累积后小于0的话就把Sum重置,每次更新Sum的最大值。最后便能求出最大值。
其实这个算法就是把序列分为好几块,每一块满足:对于任意k,前k个数的和不会小于0(小于0就没有和后面的数列连续的价值了),当前i个数的和大于最大值时就进行更新,而最大值的左边界就是该块序列的第一个,右边界是第i个。
时间复杂度为O(n),而且可以一边读取一边处理,不需要开数组来存,空间也很省。
代码如下:
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int maxn=100005; int main() { int t,n; while(scanf("%d",&n)&&n!=0) { int max=-1111111,b=-111111; for(int i=1;i<=n;i++) { scanf("%d",&t); if(b<0) b=t; else { b+=t; } if(b>max) max=b; } printf("%d\n",max); } }方法四:动态规划O(n),效率同样很高。
算法思想:
设s[j]表示第j处,以a[j]结尾的子序列的最大和。
注意:dp[j]并不是前j-1个数中最大的连续子序列之和,而只是包含a[j]的最大连续子序列的和。我们求出b[j]中的最大值,即为所求的最大连续子序列的和。
递推公式:dp[j]=max{dp[j],dp[j-1]+a[j]};
代码:
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int maxn=10005; int a[maxn],dp[maxn]; int main() { int n; while(scanf("%d",&n)!=EOF&&n!=0) { for(int i=1; i<=n; i++) { scanf("%d",&a[i]); } int max= dp[1]=a[1]; for(int i=2; i<=n; i++) { if(dp[i-1]+a[i]>=a[i]) { dp[i]=dp[i-1]+a[i]; } else { dp[i]=a[i]; } if(max<dp[i]) max=dp[i]; } printf("%d\n",max); } return 0; }
注:有时候还需要找出最大连续子序列的左右界,我这里给出第三种方法的可以求左右界的代码,以HDU1003为例。其余的方法实现,读者可以自己探究。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1003
代码:
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int maxn=100005; int a[maxn]; int main() { int t,n; while(scanf("%d",&t)!=EOF) { for( int k=1;k<=t;k++) { scanf("%d",&n); int max=-1111111,b=-111111; int l=1,ll=1,r=1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(b<0) { b=a[i]; ll=i; } else { b+=a[i]; } if(max<b) { max=b; l=ll; r=i; } } if(k<t) printf("Case %d:\n%d %d %d\n\n",k,max,l,r); else printf("Case %d:\n%d %d %d\n",k,max,l,r); } } }