首页 / 更多教程 / 多维数组求子数组最大和
多维数组求子数组最大和
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了多维数组求子数组最大和,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1121字,纯文字阅读大概需要2分钟。
内容图文
![多维数组求子数组最大和](/upload/InfoBanner/zyjiaocheng/1258/037f16c27e9c4a5c8a0b1c68a4db664d.jpg)
这一篇为上一篇一维数组的扩展:一维数组求最大和博客链接
问题:
求解二维数组的子数组中和最大的值。
代码:
// 20140319_2.cpp : Defines the entry point for the console application. // DATA:2014-03-19 // CODE:BlackSmith // 求二维数组的子数组中和最大的数组。这个是以为数组的扩展。 #include " stdafx.h " int main() { int m,n,i,j,k,z; static int q,b; int temp_sum,sum[100]; int a[100][100]; int max=0; printf("请输入数组的行数和列数\n"); scanf("%d%d",&q,&b); printf("请输入数据\n"); for(i=0;i<q;i++) { for(j=0;j<b;j++) { scanf("%d",&a[i][j]); } } for(m=0;m<q;m++) { for(k=0;k<b;k++) { sum[k]=0; } for(i=0;i<q;i++) { //将同一行的数组相加为一个数组for(j=m;j<b;j++) { sum[i]+=a[i][j]; } //一维数组的最大数组的代码for(n =0;n<b;n++) { temp_sum=0; for(z=n;z<q;z++) { temp_sum+=sum[z]; if(temp_sum>max) { max=temp_sum; } } } } } printf("最大值为%d\n",max); return0; }
具体过程:
如果不了解怎么求解一维数组的子数组的最大和问题,请参考开篇的链接。
首先我们首先任意假设一个二维数组,如图所示:4*4维
我们按照程序的思路,我们求解最大子数组的话,得想办法穷列举所有可能的子数组。我们可以接着按照一维数组的思维看待这个问题。
第一行按照一维数组的思路仍然是全部相加的和最大,然后再求第二列
然后,下一步,把一二行同列的数字相加,按照一维数组的接着算
相当于下面的图片(第一行和第二行相加以后的)
然后依次比较,这样每次就能得到相应的数据块了。
这个算法比较绕,大家可以仔细分析代码。分析出结果。
原文:http://www.cnblogs.com/renguoqing/p/3611907.html
内容总结
以上是互联网集市为您收集整理的多维数组求子数组最大和全部内容,希望文章能够帮你解决多维数组求子数组最大和所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。