資料結構
網路
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 次瀏覽
廣告