# 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 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.

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