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.
