正文

求二维数组的最大子数组———曹玉松&&蔡迎盈

IP云
IP云V管理员/3 阅读
06/21
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

继上节课老师让求了一维数组最大的子数组后，这节课堂上，老师加深了难度，给了一个二维数组，求最大子数组，开始觉得很容易，但是自己思考起来感觉这个算法很困难，既需要考虑数组直接的连续，又要求出最大的，老师提供的思路是找最大的数所在的位置是结果的可能性会大一点，或者是负数少的可能性会大一些，但这也只是一个概率问题，求解起来还是比较麻烦，也想过用二叉树，但是不能确保数组的连续性，所以只能想用一个个遍历的方法，经过自己的思考后又上网看了别人的程序，下面大家一起探讨一下吧！

#include <iostream>
#include <string>
int main(void)
{
int a[][];
int st[][];
int p,k,n,i,j,sum,max;
scanf("%d",&n);
for (i=;i<=n;i++)
for (j=;j<=n;j++)
scanf("%d",&a[i][j]);
memset(st,,sizeof(st));
for (i=;i<=n;i++)
for (j=;j<=n;j++)
st[i][j]=st[i][j-]+a[j][i];
max=;
for (i=;i<=n;i++)
{
for (j=i;j<=n;j++)
{
p=st[][j]-st[][i-];
sum=p;
for (k=;k<=n;k++)
{
if (sum>)
sum+=st[k][j]-st[k][i-];
else
sum=st[k][j]-st[k][i-];
if (sum>p)
p=sum;
}
if (p>max) maxn=p;
}
}
printf("%d\n",max);
return ;
}

常用于数组的初始化, st是一个数组，将它的所有元素初始化为0 memset(st/*数组名*/,0/*要赋予的值*/ ,sizeof(st)/*数组元素个数*/);

求二维数组的最大子数组———曹玉松&&蔡迎盈的更多相关文章

  1. 电梯调度二——曹玉松&amp&semi;&amp&semi;蔡迎盈

    电梯初步版本    经过去实际大楼的调查和一周的学习,初步完成了电梯的制作,但是这个版本的电梯功能并不是很全面,而且界面有待于改善,现在做出了测试版本,稍后进一步跟进新的版本,现在的版本初步完成的是电 ...

  2. 求二维数组最大子数组的和。郭林林&amp&semi;胡潇丹

    求二维数组子数组的最大值,开始思路不太清晰.先从最简单的开始. 以2*2的简单数组为例找规律, 假设最大数为a[0][0],则summax=a[0][0],比较a[0][0]+a[0][1].a[0] ...

  3. Problem N&colon; 求二维数组中的鞍点【数组】

    Problem N: 求二维数组中的鞍点[数组] Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 2764  Solved: 1728[Submit][S ...

  4. 蚂蚁的难题&lpar;二&rpar;首尾相连数组的最大子数组和（DP）

    蚂蚁的难题(二) 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 下雨了,下雨了,蚂蚁搬家了. 已知有n种食材需要搬走,这些食材从1到n依次排成了一个圈.小蚂蚁对每种食材 ...

  5. 求一个数组的最大子数组（C&sol;C&plus;&plus;实现）

    最大子数组:要求相连,加起来的和最大的子数组就是一个数组的最大子数组.编译环境:VS2012,顺便说句其实我是C#程序员,我只是喜欢学C++. 其实这是个半成品,还有些BUG在里面,不过总体的思路是这 ...

  6. 软件工程结对开发——返回一个整数数组中最大子数组的和（JAVA）

    题目:返回一个整数数组中最大子数组的和. 要求: 输入一个整型数组,数组里有正数也有负数: 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和: 求所有子数组的和的最大值.要求时间复杂度为 ...

  7. BOI2007 Mokia &vert; cdq分治求二维点数模板

    题目链接:戳我 也没什么,其实主要就是为了存一个求二维坐标上矩形内点的个数的模板.为了之后咕咕咕地复习使用 不过需要注意的一点是,树状数组传x的时候可千万不要传0了!要不然会一直死循环的...qwqw ...

  8. Educational Codeforces Round 41 967 E&period; Tufurama &lpar;CDQ分治 求 二维点数&rpar;

    Educational Codeforces Round 41 (Rated for Div. 2) E. Tufurama (CDQ分治 求 二维点数) time limit per test 2 ...

  9. 求解数组环中最大子数组和的问题&lpar;java&rpar;

    //石家庄铁道大学 信1405-1 班 唐炳辉 在上一次作业中,对于普通数组的最大子数组的求解问题的基础上,将普通的数组变成一个首尾相接的环,求这个环的最大子数组.类似的,只要改变普通数组的数组位置, ...

随机推荐

  1. asp&period;net配置web&period;config支持jQuery&period;Uploadify插件上传大文件

    配置web.config有两处地方需要配置,分别是集成模式和经典模式. 集成模式: <!--文件上传大小设置--> <httpRuntime requestValidationMod ...

  2. Papa Parse – 超强大的多线程 CSV 文本解析库

    Papa Parse 是一个与众不同的,在网页上运行的第一个多线程的 CSV 解析器.它可以解析千兆字节大小文件而不会导致浏览器崩溃.它能够正确地处理格式不正确或边缘的情况下的 CSV 文本.它可以分 ...

  3. C&num;&equals;&equals;&gt&semi;匿名方法 【转】

    http://blog.csdn.net/gishero/article/details/5161826 1,匿名方法 C#为委托提供一种机制,可以为委托定义匿名方法,匿名方法没有名称,编译器会定指定 ...

  4. Linux Command Line learning

    https://www.codecademy.com/en/courses/learn-the-command-line Background The command line is a text i ...

  5. 【原】IOS兼容性之APP内fixed定位头部跳动

    兼容现象: 在App的webview里边,我们有时候会在页面里写自定义头部,会使用到fixed定位,我们想要的效果是,页面无论怎么滑动,这个自定义的头部始终是固定在顶部的,但是在ios 11以上的版本 ...

  6. 《清华梦的粉碎》by王垠

     清华梦的诞生 小时候,妈妈给我一个梦.她指着一个大哥哥的照片对我说,这是爸爸的学生,他考上了清华大学,他是我们中学的骄傲.长大后,你也要进入清华大学读书,为我们家争光.我不知道清华是什么样子,但是我 ...

  7. 转&colon;&sol;&sol;linux下的CPU、内存、IO、网络的压力测试工具与方法介绍

    转载地址:http://wushank.blog.51cto.com/3489095/1585927 一.对CPU进行简单测试: 1.通过bc命令计算特别函数 例:计算圆周率 echo "s ...

  8. 20145215《网络对抗》Exp7 网络欺诈技术防范

    20145215<网络对抗>Exp7 网络欺诈技术防范 基础问题回答 通常在什么场景下容易受到DNS spoof攻击? 在同一局域网下比较容易受到DNS spoof攻击,攻击者可以冒充域名 ...

  9. Python垃圾回收机制及gc模块详解：内存泄露的例子

    标记清理是用来解决循环引用的.分代回收针对所有的新创建即进入0代的对象和进入1.2代的对象..这样就解释了python“引用计数为主.标记清理+分代回收为辅”的垃圾回收原理,因为循环引用毕竟是少数情况 ...

  10. Rails 5 Test Prescriptions 第5章 Testing Models

    Rails,model层包含业务逻辑和储存逻辑.其中储存逻辑被ActiveRecord处理. 在model中,不是每件事都必须是ActiveRecord对象.model layer可以包含各种服务,对 ...