একটি ২ডি অ্যারে দেওয়া আছে। যেকোনো সাব-ম্যাট্রিক্সের মেইন ডায়াগোনালের উপাদানগুলোর যোগফল (ট্রেস) এর সর্বোচ্চ মান বের করতে হবে।
উদাহরণ
arr[][] = {{-2,5,3}, {1,6,2}, {4,3,9}}
আউটপুট: 15
ব্যাখ্যা: সাব-ম্যাট্রিক্স {{1,6},{9,3}} এর ট্রেস = 1+3? না, সঠিক সাব-ম্যাট্রিক্স হলে ট্রেস ১৫ হয়।
অ্যালগরিদম
- প্রতিটি সেল (i,j) কে সাব-ম্যাট্রিক্সের টপ-লেফট ধরে ডায়াগোনাল স percorrer করুন।
- প্রতিটি ডায়াগোনালের জন্য রানিং সম নিন এবং সর্বোচ্চ ট্র্যাক রাখুন।
- টাইম কমপ্লেক্সিটি: O(N³) (N x N ম্যাট্রিক্সের জন্য)।
C++ প্রোগ্রাম
#include <iostream>
using namespace std;
#define ROW 3
#define COL 3
int CalcMaxTraceSubMat(int mat[ROW][COL]) {
int maxTrace = 0;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
int r = i, c = j, traceSum = 0;
while (r < ROW && c < COL) {
traceSum += mat[r][c];
maxTrace = max(maxTrace, traceSum);
r++; c++;
}
}
}
return maxTrace;
}
int main() {
int mat[ROW][COL] = {{-2,5,6}, {1,6,2}, {4,3,9}};
cout << "Maximum trace of any submatrix: " << CalcMaxTraceSubMat(mat);
return 0;
}
আউটপুট: Maximum trace of any submatrix is 15
