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
热门推荐
10 新年门口花束祝福语简短
11 盘锦结婚祝福语大全简短
12 父母生日祝福语 简短独特
13 家庭恩爱祝福语简短英文
14 高考俄语祝福语大全简短
15 虎年祝福语 诗句唯美简短
16 生日婚礼祝福语简短精辟
17 虎年喝酒拜年祝福语简短
18 教师闺蜜祝福语简短