题目地址：http://ac.jobdu.com/problem.php?pid=1497
- 题目描述：
- 在一个M * N的矩阵中，所有的元素只有0和1，从这个矩阵中找出一个面积最大的全1子矩阵，所谓最大是指元素1的个数最多。
- 输入：
- 输入可能包含多个测试样例。
对于每个测试案例，输入的第一行是两个整数m、n(1<=m、n<=1000)：代表将要输入的矩阵的大小。
矩阵共有m行，每行有n个整数，分别是0或1，相邻两数之间严格用一个空格隔开。
- 输出：
- 对应每个测试案例，输出矩阵中面积最大的全1子矩阵的元素个数。
- 样例输入：
-
2 2 0 0 0 0 4 4 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
- 样例输出：
-
0 4
1. 动态规划——三个状态数组，分别保存当前点的高度up，左边界left，右边界right，max_value=https://www.it610.com/article/max(max_value,up*(right-left+1)；
#include
using namespace std;
#include #define N 1000bool data[N][N];
int up[N][N];
int l_flag[N][N];
int r_flag[N][N];
int main()
{
int m,n;
int max_1;
int l_num,r_num;
while(cin>>m>>n)
{
for(int i=0;
i>data[i][j];
max_1=0;
for(int i=0;
i=0;
j--)
{
if(!data[i][j])
{
r_flag[i][j]=n;
r_num=j;
}
else
{
if(i==0)
r_flag[i][j]=r_num-1;
else
r_flag[i][j]=min(r_num-1,r_flag[i-1][j]);
}
max_1=max(max_1,up[i][j]*(r_flag[i][j]-l_flag[i][j]+1));
}
}
cout< 2.向右得到每个点左边连续1的个数，如 0 1 0 1 1 0 -> 0 1 0 1 2 0。然后算每列的最大1矩阵，例如：
某列 为 1 2 3 3 4 2 0 ，得到最大1矩阵为2*5=10，具体方法为对每个元素分别向上（左）向下（右）查询连续大于等于自己的元素个数，然后相乘
此方法在九都测试超时，但是结果是对的。
【腾讯面试题（九度）——面积最大的全1子矩阵】
#include
using namespace std;
#include bool data[1000][1000];
int flag[1000][1000];
int main()
{
int m,n;
int max_1,value,depth;
int x;
while(cin>>m>>n)
{
for(int i=0;
i>data[i][j];
if(data[i][j])
{
if(j==0)
flag[i][j]=1;
else
flag[i][j]=flag[i][j-1]+1;
}
else
flag[i][j]=0;
}
max_1=0;
for(int j=0;
j0)
{
if(flag[--x][j]>=value)
depth+=1;
else
break;
}
x=i;
while(x=value)
depth+=1;
else
break;
}
max_1=max(max_1,depth*value);
}
}
cout< 推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络