从一个m×n的整数矩阵中,找到x×y的子矩阵,使子矩阵中所有元素的和最大,并输出和及子矩阵所有元素。算法实现的思路是怎么样的?
4条回答
- M醉清风Y 2016-02-26 12:38关注
遍历M * N 的数组 中所有 X * Y矩阵集合 然后记录最大值,返回
给你写个 伪代码:
引用你的 m n x y 的值 架设 array为 你的二维数组
if(x <=0 || x> m || y <=0 || y>n) return;
int sum = 0;
int sumMax = 0; //记录最大值
int x_index = 0;//记录 X 坐标
int y_index = 0;//记录Y 坐标
int Pos_w = m - x + 1; //计算出 矩阵横向移动次数
int Pow_h = m - y + 1;//计算出 矩阵竖向移动次数
for(int i= 0 ;i< Pos_w *Pow_h; ++i)
{
sum = 0; //清空
//获取该子矩阵的和
for(int j = 0; j < x * y; ++j)
{
sum += array[j / x + i / Pos_w, j % x + i%Pos_w];
}
if (sum > sumMax)
{
x_index = i % Pos_w;
y_index = i / Pos_w;
sumMax = sum;
}
}
你只要 用 x_index 和 y_index 就可以了 记住 这个 坐标 记录的是 你所需要的子矩阵中 左上角的坐标 从 0,0开始。
Y 代表 矩阵中的第几行 X 代表 第几列。 我在写运算的时候 已经把 二维转换成 一维了,优化代码的作用。
如果不理解的话 可以在问我 你直接套用即可。本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥60 求一个简单的网页(标签-安全|关键词-上传)
- ¥35 lstm时间序列共享单车预测,loss值优化,参数优化算法
- ¥15 基于卷积神经网络的声纹识别
- ¥15 Python中的request,如何使用ssr节点,通过代理requests网页。本人在泰国,需要用大陆ip才能玩网页游戏,合法合规。
- ¥100 为什么这个恒流源电路不能恒流?
- ¥15 有偿求跨组件数据流路径图
- ¥15 写一个方法checkPerson,入参实体类Person,出参布尔值
- ¥15 我想咨询一下路面纹理三维点云数据处理的一些问题,上传的坐标文件里是怎么对无序点进行编号的,以及xy坐标在处理的时候是进行整体模型分片处理的吗
- ¥15 CSAPPattacklab
- ¥15 一直显示正在等待HID—ISP