记录学习过程中的点点滴滴
最大子段和、最大子矩阵和、最大m子段和问题总结
1,最大子段和问题
代码:
int MaxSum(int n,int *a) { int sum = 0; int b = 0,i; for(i=0;i<n;i++) { if(b>0) b+=a[i]; else b = a[i]; if(b>sum)sum = b; } return sum; }
2,最大子矩阵和问题
代码:
int MaxSum2(int m,int n,int** a) { int sum = 0,i,j,k; int b[105]; for(i=0;i<m;i++) { for(k=0;k<n;k++) { b[k] = 0; } for(j=i;j<m;j++) { for(k=0;k<n;k++) { b[k]+=a[j][k]; } int mx = MaxSum(n,b); if(sum<mx)sum=mx; } } return sum; }
3,最大m子段和问题
double b[50005]; double c[50005]; int MaxSum3(int m,int n,int* a) { int i,j,k,mx,sum; b[0] = 0; c[0] = 0; for(i=1;i<=m;i++) { b[i] = b[i-1] + arr[i]; c[i-1] = b[i]; mx = b[i]; for(j=i+1;j<=i+n-m;j++) { b[j] = b[j-1]>c[j-1]?b[j-1]+arr[j]:c[j-1]+arr[j]; c[j-1] = mx; if(mx<b[j]) { mx = b[j]; } } c[i+n-m] = mx; } sum = b[m]; for(k=m+1;k<=n;k++) { if(sum<b[k])sum=b[k]; } return sum; }
本文地址:http://www.yaronspace.cn/blog/?p=43
来自yaronspace.cn 本文链接:http://yaronspace.cn/blog/archives/43您可能对下面文章也感兴趣:
这篇文章由admin于2009 年 10 月 30 日 22:24发表在编程语言与算法设计。你可以订阅RSS 2.0 也可以发表评论或引用到你的网站。 |