题目描述：
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 × 1)子矩阵。
比如，如下4 × 4的矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩阵是
9 2
-4 1
-1 8
这个子矩阵的大小是15。
输入：
输入是一个N×N的矩阵。输入的第一行给出N(0<N≤100)。再后面的若干行中，依次(首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127]。
输出：
输出最大子矩阵的大小。
样例：
输入：
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
输出：
15
思路：
我们都知道在一维情况下求最大连续子序列和的操作其实就是求最大连续子序列：
for(int i=1;i<=n;i++)
{
dp[i]=max(a[i],dp[i-1]+a[i]);
}
那么该怎么推广到二维情况下呢：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
步骤：
1. 求矩阵1*k（k=1,2,3,4)
就是求每行的最大连续子序和
0 -2 -7 0 ans=0
9 2 -6 2 ans=11
-4 1 -4 1 ans=1
-1 8 0 -2 ans=8
2. 求矩阵大小是2*k（k=1,2,3,4）
这时我们可以在第1,2行或2,3行或3,4行找最大矩阵
例如：
0 -2 -7 0
9 2 -6 2
因为取的是矩阵，肯定是竖着一列都取的，不可能这一列取到第i个元素，上一列取到第i-1个元素，这样我们就可以把要求的两行，两两加起来
9 0 -13 2
这样求出的最大连续子序和是9，这个结果也就是这个矩阵对应的最大矩阵和。
同理把
9 2 -6 2
-4 1 -4 1
和
-4 1 -4 1
-1 8 0 -2
也分别加起来，三种情况下求出的最大值，就是2*k大小矩阵的最大值
3. 3 * k和4 * k的矩阵也是这样，最后求出最大子矩阵
代码如下：
#include <iostream>
#include <cstring>
using namespace std;
int a[105][105],b[105][105],dp[105];//b[j][k]表示从i行加到j行 第k列值的大小，将二维转为一维
int ans,n;
void solve(int j)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
dp[i]=max(b[j][i],b[j][i]+dp[i-1]);
ans=max(ans,dp[i]);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++)//从第i行开始加
{
memset(b,0,sizeof(b));
for(int j=i;j<=n;j++)//加到第j行
{
for(int k=1;k<=n;k++)//第k列
{
b[j][k]=a[j][k]+b[j-1][k];
}
solve(j);
}
}
cout<<ans<<endl;
return 0;
}
文章浏览阅读3.1k次。在现代应用程序中，认证已不再是简单的将用户凭证保存在浏览器中，而要适应多种场景，如App，WebAPI，第三方登录等等。在 ASP.NET 4.x 时代的Windows认证和Forms认证已无法满足现代化的需求，因此在ASP.NET Core 中对认证及授权进行了全新设计，使其更加灵活，可以应付各种场景。在上一章中，我们提到HttpContext中认证相关的功能放在了独立的模块中，以扩展的方式来展_.net core authenticationhandler httpcontext
文章浏览阅读1.5w次。初始代码public Map&lt;String,List&lt;RgwstBean&gt;&gt; getMap(List&lt;RgwstBean&gt; lists){ Map&lt;String,List&lt;RgwstBean&gt;&gt; map = new TreeMap&lt;String,List&am_list转成map且顺序不变
文章浏览阅读5.9k次，点赞5次，收藏16次。leaflet通过WFS服务加载geoserver 矢量数据1.前言2.从geoserver获得geojson数据3.geoserver跨域配置4.根据请求结果生成layer5.完整代码1.前言leaflet默认支持的服务只有WMS，因此不能加载WFS数据，但是leaflet提供了另一个方法geoJson，它的作用是从一个geojson文件中加载地图，所以利用leaflet加载WFS数据的一个..._leaflet geoserver wfs 方式
文章浏览阅读937次。开发工具与关键技术：VS，MVC作者：陈梅撰写时间：2019年6月2 日所有代码来源与老师教学这次分享一个好玩的自定义动画效果，这次还是用jQuery做出来的小功能。这次我们先直接看最后已经布局好的效果。把所想写的内容填写到p标签中，给到p标签的动画功能是，页面已执行时，p标签的内容就会渐渐消失。在给一个紫色的div盒子，这个盒子要实现四种动画效果，所以给这四个动画效果一个下拉框，选择..._使用animate方法制作任意动画是什么意思
文章浏览阅读1k次。怎样在MongoDB实现mysql show variables like 'xx';例如:1.查看所有参数值:C:\Users\duansf>mongoMongoDB shell version: 2.6..._查看mongodb 默认参数值
文章浏览阅读863次。蚁群算法求解旅行商问题完整的代码，方可运行；可提供运行操作视频！适合小白！
文章浏览阅读2.1k次。匿名用户1级2016-09-11 回答其实吧，学习C语言是以后从事软件设计的一个基础。任何领域都需要长时间的投入才有结果，你现在学习了C语言，再学习其他语言的时候就比较上手了。在软件设计中：学习一门语言仅仅是第一阶段：如果你基本掌握了一门语言，那么再想深入学习的话就需要把所有C语言的相关的库函数弄懂，并熟练掌握一个开发平台(如最基础的TC)。这是第二阶段下一阶段你就需要继续学习不同的操作系统所提供..._c语言入门后怎么深入
文章浏览阅读672次。如果你正准备从头开始制作一个新的应用，那么React Native会是个非常好的选择。但如果你只想给现有的原生应用中添加一两个视图或是业务流程，React Native也同样不在话下。只需简单几步，你就可以给原有应用加上新的基于React Native的特性、画面和视图等。https://zjqian.github.io/2017/05/03/rn-integration-iosNative/_ios原生项目嵌入reactnative 模块
文章浏览阅读608次。本次终于写到了第五章了，前面四章节，我们从一个全新的 umi3 的ant design pro 模板开始着手，我们以一个初始者要用它的思想介入，逐步走了新增路由、cssmodules、国际化语言切换、使用mock数据进行快速开发、联调正式接口、初始化配置、登录修改、接口文件提取等等。这次到第五章了，我们暂时不做新的改变，我们来把之前写的一些杂项收拾收拾，比如，清除一些不需要的代码，规范一些东西，让我们的项目成为我们的快速开发模板。_umi 去除代码的lo
文章浏览阅读1.2k次。Android 源码编译文件中语法记录_android shell脚本语法 :>
文章浏览阅读4.2k次，点赞12次，收藏72次。1.概述Linux系统上的Video设备多种多样，如通过Camera Host控制器接口连接的摄像头，通过USB总线连接的摄像头等。为了兼容更多的硬件，Linux内核抽象了V4L2（Video for Linux Two）子系统。V4L2子系统是Linux内核中关于Video（视频）设备的API接口，是V4L（Video for Linux）子系统的升级版本。V4L2子系统向上为虚拟文件系统提供了统一的接口，应用程序可通过虚拟文件系统访问Video设备。V4L2子系统向下给Video设备提供接口，同时管理_v4l2_subdev_call
文章浏览阅读1w次。使用场景：因为在公司机房中的服务器我们在使用需要对他做一些类似于初始化的配置，分别是三个，——》第一个是配置服务器的ILO地址，这个是我们通过网络打开一个Web页面对服务器进行一些操作；——》第二个是对管理用户的密码进行修改，这个是因为不同的服务器初始的管理员的密码也许是不一样的，我们将其修改为统一的方便记忆也方便管理；——》第三个就是开启服务器的半虚拟化功能，这个是我们的公司的也许需要服..._浪潮服务器修改管理口密码