C++: Max Product in a Matrix witout Backtrack

Problem

Given a matrix, find the path from top left to bottom right with the greatest product by moving only down and right.

The code is in C++.
The only moves allowed are down and right. The solution works for positive numbers.

#include <iostream>
using namespace std;
void printMatrix(int **matrix, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++)
cout << matrix[i][j] << " ";
cout << endl;
}
}
int matrixProduct(int matrix[][3], int r, int c) {
// check for zero sized matrix
if (r == 0 && c == 0) {
return 0;
}
int **maxCache = new int*[r];
for (int i =0 ; i < r; i++) {
maxCache[i] = new int[c];
}
int temp1=0, temp2=0;
for (int i = 0; i < r; i++) {
for(int j = 0; j < c; j++) {
if (i == 0 && j == 0) {
maxCache[i][j] = matrix[i][j];
continue;
}
if (i > 0) {
temp1 = maxCache[i-1][j]*matrix[i][j];
}
if (j > 0) {
temp2 = maxCache[i][j-1] * matrix[i][j];
}
maxCache[i][j] = max(temp1, temp2);
temp1 = temp2 = -1;
}
}
// print matrix
printMatrix(maxCache, r, c);
return maxCache[r-1][c-1];
}
int main() {
int matrix[][3] = {{1,2,3},{4,5,6},{7,8,9}};
cout << matrixProduct(matrix, 3,3) << endl;
}

Reference

Written with StackEdit.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: