一,题目:
求一个矩阵中最大的二维矩阵(元素和最大).如:
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;
}
分享到:
相关推荐
标题中的“求一矩阵中子矩阵的最大和”是一个经典的计算机科学问题,通常称为“找到一个矩阵中的最大子矩阵和”。这个问题在数据结构和算法领域有着广泛的应用,特别是在处理大规模数据时寻找局部最优解的问题上。 ...
总之,矩阵相加是线性代数中一个基本且重要的运算,通过C语言编程实现矩阵相加,不仅加深了我们对矩阵和二维数组的理解,还提高了我们的编程技能。在实际应用中,矩阵相加广泛应用于图像处理、信号处理、数据分析等...
本文将深入探讨如何从三维矩阵中提取出任意二维的数据,并将其保存到新的二维矩阵中,同时讨论如何灵活地变换顺序。 首先,三维矩阵在MATLAB中通常表示为大小为[m x n x p]的数组,其中m、n和p分别代表矩阵的三个...
程序功能:从三维数组中提取出任意二维的数据,并保存在新的二维矩阵中,且能所以变换顺序。
在这个特定的案例中,"使用二维网格和二维块对矩阵求和"是一种优化的CUDA编程技术,用于提高矩阵求和的效率。 二维网格(2D Grid)是CUDA并行计算的基本组织结构之一,它由多个线程块(Thread Blocks)组成,这些...
例如,可以创建一个二维的int数组,如`int matrix[2][3]`,或者定义一个包含两行三列元素的类,类内包含一个二维指针或者vector容器。 3. **矩阵加法**:两个矩阵相加的条件是它们必须有相同的维度。对于给定的2行3...
编写一个在具有m行n列的二维数组各元素中找出最大元和最小元并显示在屏幕上的函数模板,并通过主函数对它进行调用以验证其正确性。例如,可设计该函数模板的原型为: template <class Type> void maxMin (Type *A,...
在编程领域,鞍点(Saddle Point)是指在一个矩阵中,某个元素在同一行中最大,同时在同一列中最小。这是一个相对特殊的位置,因为通常我们关注的是最大值或最小值,而鞍点则结合了这两种特性。在Java编程中,解决这...
代码中使用了动态内存分配来创建两个二维数组`firstTemp`和`secondTemp`,用于存储输入的矩阵数据,以及一个额外的二维数组`printTemp`用于存放两个矩阵相加的结果。动态内存分配是通过`new`关键字完成的,这使得...
二维离散傅里叶变换(2D Discrete Fourier Transform,简称2D DFT)是数字信号处理中的一个重要概念,主要用于分析图像或矩阵数据的频域特性。它将图像或矩阵的时域(空间域)表示转换为频域表示,揭示了数据在不同...
第一行分别为矩阵的行数m和列数n(m<100,n<100),两者之间以一个空格分开。 接下来输入的m行数据中,每行包含n个整数,整数之间以一个空格分开。 【输出】 输出对应矩阵的边缘元素和。 【输入样例】 3 3 3 4 1 ...
总的来说,二维沃尔什矩阵变换是数字信号处理领域中的一个重要工具,其理论基础和实际应用都相当广泛。MATLAB脚本"walsh2d.m"则提供了一个便捷的实现方式,便于研究者和工程师在各种场景下使用这一技术。
Java 求一个3*3矩阵对角线元素之和,实现的思路主要是利用双重for循环控制输入二维数组,再将a[i][i]累加后输出。也就计算对角线之和。计算对角线之和代码分享: for(int i = 0;i ;i ) { for(int j = 0;j ;j ...
使用二维数组和双重循环打印蛇形矩阵使用二维数组和双重循环打印蛇形矩阵使用二维数组和双重循环打印蛇形矩阵
在二维空间中,我们可以使用一个3x3的平移矩阵,其中对角线元素为1,最后一行的前两个元素为0,最后一个元素为平移距离(在X轴和Y轴上的量)。 2. 旋转:旋转变换使得图形围绕一个固定点(称为旋转中心)转动。旋转...
在IT领域,尤其是在编程中,二维矩阵、排序和递归是三个非常重要的概念。这篇文本将深入探讨这些知识点,结合给定的文件名"jioupaixu"(可能表示“角排序”或“九排序”)、"digui"(递归)和"erweijuzhen"(二维...
二维矩阵是计算机科学和数学中的基础概念,特别是在线性代数、图像处理、编程和数据分析等领域广泛应用。在本文中,我们将深入探讨二维矩阵的概念、性质、运算以及它们在实际问题中的应用。 首先,二维矩阵是一种...
二维矩阵转一维矩阵 * 以列为主,loc=column+row*行数 * 以行为主,loc=row+column*列数 * 三维矩阵转一维矩阵,i(u1个数),j(u2个数),k(u3个数)分别表示三维矩阵 * 以列为主,loc=i*u2*u3+j*u3+k; * 以行为主,...
二维图形的矩阵变换是计算机图形学中的重要概念,它在游戏开发、图像处理、动画制作等领域有着广泛应用。本文将深入探讨如何使用矩阵变换实现“北极星”图案的五种基本变换:平移、比例、旋转、错切和对称。 首先,...
注意,为了节省空间,我们使用一维数组表示二维矩阵,通过行索引乘以列数得到元素在数组中的下标。 这个算法的时间复杂度是O(n^2),其中n是矩阵的元素数量。虽然不是最优的,但对小规模矩阵而言,效率足够高。对于...