DP-最大子矩阵
2024-10-21 23:18:08
1768:最大子矩阵
题目描述:
描述已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是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
参考:https://www.cnblogs.com/shadowland/p/5870382.html
枚举子矩阵时先确定最左侧一列和最右一列,即左右边界,然后把子矩阵每一行的值求和,压缩成一个一维数组,对这个数组求最大字段和。
i=1
i=2
源代码:
#include<iostream>
#include<cstring>
using namespace std; int main()
{
int a[105][105],dp[105]={0};
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
int ans=-1e10;
for(int i=1;i<=n;i++)
{
memset(dp,0,sizeof(dp));
for(int j=i;j<=n;j++)//从第i列开始的情况
{
int t=0;
for(int k=1;k<=n;k++)//相加第j行
{
dp[k]+=a[j][k]; if(t<=0)//累加值已变为负,要求最大值删去之前的累加值
{
t=dp[k];
}
else
{
t+=dp[k];
}
if(t>ans)
{
ans=t;
}
} } }
cout<<ans<<endl;
return 0;
}
最新文章
- LR中线程和进程的区别
- android 中调用接口发送短信
- WPF自定义控件与样式(15)-终结篇 &; 系列文章索引 &; 源码共享
- Enum遇到下拉框
- Makefile的学习笔记
- php中cookie+mysql实现的购物车代码
- Ubuntu14.04安装配置ndnSIM
- perl 线程创健
- React Links
- Canvas--2
- elasticsearch快照和恢复
- Spring Cache扩展:注解失效时间+主动刷新缓存
- 模板 m&#250; bǎn
- GlideNewDemo【Glide4.7.1版本的简单使用以及圆角功能】
- H5页面移动端IOS键盘收起焦点错位
- ReentrantReadWriteLock 读写锁解析
- 使用jackson来进行数组格式的json字符串转换成List。
- 方法装饰器(Decorator)
- SQL Server2005/2008 作业执行失败的解决办法
- ZH奶酪:哈工大LTP云平台标记含义及性能