数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时装研究
法律研究用 C++ 求出给定矩阵中任何子矩阵可能的最大的迹
在这个问题中，我们获得了二维数组 arr[][]. 我们的任务是创建一个程序以用 C++ 求出给定矩阵中任何子矩阵可能的最大迹。
问题描述
我们需要找出任何子矩阵的最大迹。迹是矩阵主对角线元素的总和。
我们举一个例子来理解这个问题，
输入
arr[][] ={{-2, 5, 3},
{1, 6, 2},
{4, 3, 9}}输出
15
解释
For the sub-array: {1, 6}
{9, 3}解决方案方法
一种简单的解决方案是使用二维数组主对角线的元素找到最大总和。迹由最大子数组和给出。
示例
一个程序来说明我们解决方案的工作原理，
#include <iostream>
using namespace std;
#define row 3
#define col 3
int CalcMaxTraceSubMat(int mat[row][col]){
int maxtraceSum = 0, r, c, traceSum;
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
r = i, c = j, traceSum = 0;
while (r < row && c < col){
traceSum += mat[r][c];
r++;
c++;
maxtraceSum = max(traceSum, maxtraceSum);
}
}
}
return maxtraceSum;
}
int main() {
int mat[row][col] = { {-2, 5, 6},
{1, 6, 2},
{4, 3, 9} };
cout<<"The maximum trace possible for any submatrix is "<<CalcMaxTraceSubMat(mat);
return 0;
}输出
The maximum trace possible for any submatrix is 15
更新时间： 2020 年 10 月 15 日
273 次浏览
广告