题目描述：
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是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;
}
文章浏览阅读227次。随着业务的快速扩张，原本小作坊式的单个工程的开发模式越来与不能满足实际需求。早在两年多以前，51信用卡管家就向下沉淀出了单独的公用基础库，一些通用的功能组件和个别独立的业务被拆分成 SDK，形成了一套中型项目、多人并行的开发模式，也为未来组件化拆分做准备。这套框架运行了一段时间之后，伴随着单应用内业务需求的增加、开发人员数量的增多、基础库数量的膨胀，导致了一些问题：主工程代码耦合严重，牵一发而动全...
文章浏览阅读1.5w次，点赞10次，收藏129次。文章目录目录模型评估评价指标1.分类评价指标acc、recall、F1、混淆矩阵、分类综合报告1.准确率方式一：accuracy_score方式二：metrics2.召回率3.F1分数4.混淆矩阵5.分类报告6.kappa scoreROC1.ROC计算2.ROC曲线3.具体实例2.回归评价指标3.聚类评价指标1.Adjusted Rand index 调整兰德系数2.Mutual Informa..._model.score
文章浏览阅读344次。因工作需要，在Apache上使用，重新学习配置mod_jk1. 分别安装Apache和Tomcat：2. 编辑httpd-vhosts.conf： LoadModule jk_module modules/mod_jk.so #加载mod_jk模块 JkWorkersFile conf/workers.properties #添加worker信息 JkLogFil_apache mod_jk 虚拟
文章浏览阅读335次。待老夫kotlin大成,扩展:MotionLayout 与 CoordinatorLayout,DrawerLayout,ViewPager 的 交互众所周知,MotionLayout 的 动画是有完成度的 即Progress ,他在0-1之间变化,一.CoordinatorLayout 与AppBarLayout 交互时,其实就是监听 offsetliner 这个 偏移量的变化 同样..._android onoffsetchanged
文章浏览阅读8.3k次，点赞3次，收藏19次。【转】多核处理器的工作原理及优缺点《处理器关于多核概念与区别 多核处理器工作原理及优缺点》原文传送门 摘要：目前关于处理器的单核、双核和多核已经得到了普遍的运用，今天我们主要说说关于多核处理器的一些相关概念，它的工作与那里以及优缺点而展开的分析。1、多核处理器 多核处理器是指在一枚处理器中集成两个或多个完整的计算引擎（内核），此时处理器能支持系统总线上的多个处理器，由总..._多核处理器怎么工作
文章浏览阅读306次。1. eclipse配置lombok 拷贝lombok.jar到eclipse.ini同级文件夹下，编辑eclipse.ini文件，添加: -javaagent:lombok.jar2. myeclipse配置lombok myeclipse像eclipse配置后，定义对象后，直接访问方法，可能会出现飘红的报错。 如果出现报错，可按照以下方式解决。 ..._eclispe每次运行个新项目都需要重新配置lombok吗
文章浏览阅读7.8k次，点赞2次，收藏17次。在实际的项目开发中，我们通常会用到Echarts来对数据进行展示，有时候需要用到Echarts的点击事件，增加系统的交互性，一般是点击Echarts图像的具体项来跳转路由并携带参数，当然也可以根据具体需求来做其他的业务逻辑。下面就Echarts图表的点击事件进行实现，文章省略了Echarts图的html代码，构建过程，option，适用的表格有饼图、柱状图、折线图。如果在实现过程中，遇到困难或者有说明好的建议，欢迎留言提问。_echarts 饼图点击事件
文章浏览阅读1.3k次，点赞4次，收藏14次。内容整理自，华中科技大学，苏曙光老师《操作系统原理》，可在MOOC课程学习相关课程。_操作系统课程思维导图
文章浏览阅读4.3k次。vite在开发阶段采用的是按需加载的方式，不会将所有文件打包。但是生产环境的部署是需要进行打包的，这里它使用的是rollup打包方式。对于代码切割的需求，使用原生动态导入，因此打包后支持新浏览器，对IE的兼容性不是很好，但是可以用对应的polyfill解决。使用esbuild来处理需要pre-undle的在cli.ts的build命令中引入build.ts调用doBuild方法，在这个方法中配置打包参数（input output plugin等）调用buildHtmlPlugin解析文件入口in_vite build
文章浏览阅读1.4k次。http://blog.csdn.net/pipisorry/article/details/52902234Scala 访问修饰符Scala 访问修饰符基本和Java的一样，分别有：private，protected，public。如果没有指定访问修饰符符，默认情况下，Scala对象的访问级别都是 public。Scala 中的 private 限定符，比 Java 更严格，在嵌套类情况下，外层_scala ===运算符
文章浏览阅读2.6k次，点赞7次，收藏19次。ER图导出为PDF或图片格式_数据库怎么导出er图
文章浏览阅读655次。CREATE OR REPLACE TRIGGER Trg_ReimFactBEFORE UPDATEON BP_OrderFOR EACH ROWDECLAREPRAGMA AUTONOMOUS_TRANSACTION;--自制事务fc varchar2(255);BEGINIF ( :NEW.orderstate = 2AND :NEW.TransState = 1 ) THENBEG..._oracle触发器更新同一张表