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.