一,题目:
求一个矩阵中最大的二维矩阵(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码
二,分析:
假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵,
如下所示(ari表示a[r][i],假设数组下标从1开始):
| a11 …… a1i ……a1j ……a1n |
| a21 …… a2i ……a2j ……a2n |
.....
| ar1 …… ari ……arj ……arn |第r行
. . .
.......... |
V
| ak1 …… aki ……akj ……akn | 第k行 . . .
.....
| an1 …… ani ……anj ……ann |
那么我们将从第r行到第k行的每一行中相同列的加起来,可以得到一个一维数组如下:
(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)
由此我们可以看出最后所求的就是此一维数组的最大子段和问题,
到此我们已经将问题转化为上面的已经解决了的问题了。
三,源码(以下源码是求n行n列矩阵最大子矩阵代码)
#include <iostream>
using namespace std;
int maxSubArray(int a[],int n)
{
int b=0,sum=a[0];
for(int i=0;i<n;i++)
{
if(b>0)
b+=a[i];
else
b=a[i];
if(b>sum)
sum=b;
}
return sum;
}
int maxSubMatrix(int array[][3],int n)
{
int i,j,k,max=0,sum=-100000000;
int b[3];
for(i=0;i<n;i++)
{
for(k=0;k<n;k++)//初始化b[]
{
b[k]=0;
}
for(j=i;j<n;j++)//把第i行到第j行相加,对每一次相加求出最大值
{
for(k=0;k<n;k++)
{
b[k]+=array[j][k];
}
max=maxSubArray(b,k);
if(max>sum)
{
sum=max;
}
}
}
return sum;
}
int main()
{
int n=3;
int array[3][3]={{1,2,3},{-1,-2,-3},{4,5,6}};
cout<<"MaxSum: "<<maxSubMatrix(array,n)<<endl;
}
分享到:
相关推荐
程序功能:从三维数组中提取出任意二维的数据,并保存在新的二维矩阵中,且能所以变换顺序。
编写一个在具有m行n列的二维数组各元素中找出最大元和最小元并显示在屏幕上的函数模板,并通过主函数对它进行调用以验证其正确性。例如,可设计该函数模板的原型为: template <class Type> void maxMin (Type *A,...
二维矩阵二维矩阵二维矩阵二维矩阵二维矩阵二维矩阵二维矩阵二维矩阵二维矩阵
二维数组计算矩阵相加,希望大家看看,共同学习啊。
第一行分别为矩阵的行数m和列数n(m<100,n<100),两者之间以一个空格分开。 接下来输入的m行数据中,每行包含n个整数,整数之间以一个空格分开。 【输出】 输出对应矩阵的边缘元素和。 【输入样例】 3 3 3 4 1 ...
从三维数组中提取出任意二维的数据,并保存在新的二维矩阵中,且能所以变换顺序。
35. 求一个矩阵中最大的二维矩阵(元素和最大).如: 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0 中最大的是: 4 5 5 3 要求:(1)写出算法;(2)分析时间复杂度;
Java 求一个3*3矩阵对角线元素之和,实现的思路主要是利用双重for循环控制输入二维数组,再将a[i][i]累加后输出。也就计算对角线之和。计算对角线之和代码分享: for(int i = 0;i ;i ) { for(int j = 0;j ;j ...
使用二维数组和双重循环打印蛇形矩阵使用二维数组和双重循环打印蛇形矩阵使用二维数组和双重循环打印蛇形矩阵
二维矩阵转一维矩阵 * 以列为主,loc=column+row*行数 * 以行为主,loc=row+column*列数 * 三维矩阵转一维矩阵,i(u1个数),j(u2个数),k(u3个数)分别表示三维矩阵 * 以列为主,loc=i*u2*u3+j*u3+k; * 以行为主,...
用于matlab寻找三维图像或二维矩阵的波峰,详细使用方法可在 https://github.com/JamesHoi/Matlab/tree/master/IMMC/Findpeaks 查看。此资源免费下载,我的更多资源可在 ...
基于OpenCV的二维矩阵刚性变换(旋转,平移),已知两点集,求解R&T变换矩阵,其中自定义接口,已经赋初值,可以更改调用
如果矩阵A中存在这样的一个元素A[i][j]满足条件“A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素”,则称之为该矩阵的一个马鞍点。编写一个函数,计算出m*n的矩阵A的所有马鞍点
设 其中 计算步骤:对图像按行执行次一维得到 对矩阵按列执行次一维得到 计算步骤:对频率矩阵按行执行次一维得到 对矩阵按列执行次一维得到。
找出一个二维数组的鞍点,即该位置上的元素在该行上最大、在列上最小(也可能没有鞍点)。
获取两个二行三列的矩阵并计算两个二行三列的矩阵的和,输出结果
用C++二维数组做的两个矩阵相加 没有考虑任何条件
根据邻接矩阵求最大连通分支的MATLAB函数,输入为邻接矩阵,输出为最大连通分支点集。
php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵...
实例2:创建一个二维矩阵并计算其均方根值 实例3:计算二维矩阵沿指定维度的均方根值 本资源配套CSDN博客“Matlab结果性能评价---rms函数(计算矩阵、数组和向量元素均方根)”,可 前往查看具体原理和实现效果!!!...