Maximum trace possible for any sub-matrix of the given matrix in C++

In this problem, we are given a two-dimensional array arr[][]. Our task is to create a program to find the Maximum trace possible for any sub-matrix of the given matrix in C++.

Problem Description

we need to find the maximum trace for any sub-matrix. The trace is the sum of elements of the main diagonal of the matrix.

Let’s take an example to understand the problem,

Input

arr[][] ={{-2, 5, 3},           {1, 6, 2},           {4, 3, 9}}

Output

15

Explanation

For the sub-array: {1, 6} {9, 3}

Solution Approach

A simple solution is to find the max sum using the element of the main diagonal of the 2-D array. The trace is given by the max subarray sum.

Example

Program to illustrate the working of our solution,

 Live Demo

#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; }

Output

The maximum trace possible for any submatrix is 15