Comment on page
Maximum Product in Matrix
Given a 2D matrix find the path with the maximum product. Make the simplifying assumption that the elements are always positive. Return both the maximum product, and the path (the elements that produce this product). As shown in the table below, an available path for an element is defined by it's 3 or 2 closest elements below it,. Discuss how you would approach with problem with negative elements allowed.
left | | | | center | | | | right |
[r, c] | | | | [r,c] | | | | [r,c] |
[r+1,c] | [r+1, c+1] | | [r+1,c-1] | [r+1,c] | [r+1,c+1] | | [r+1, c-1] | [r+1,c] |
The Idea: See seam carving with dynamic programming, the idea is effectively the same.
Complexity: O(n*m) time and space
import numpy as np
def max_product_path(m):
n_row = m.shape[0]
n_col = m.shape[1]
m_wrap = np.zeros((n_row+2, n_col+2))
m_wrap[1:n_row+1, 1:n_col+1] = m
# dp max path
for i in range(2, len(m_wrap)-1):
for j in range(1, len(m_wrap)-1):
m_wrap[i][j] *= max(m_wrap[i-1][j-1], m_wrap[i-1][j], m_wrap[i-1][j+1])
# return the maximum product on bottom row
max_product = max(m_wrap[m_wrap.shape[0]-2, :])
# backtrack to find the maximum path
focus = m_wrap[1:n_row+1, 1:n_col+1]
cur_row = len(focus)-1
max_start_i = np.argmax(focus[cur_row, :])
max_path = [m[cur_row, max_start_i]]
cur_row -= 1
while cur_row >= 0:
max_i = np.argmax(focus[cur_row, :])
max_path.append(m[cur_row, max_i])
cur_row -= 1
return max_product, max_path
ex1 = np.matrix('1 3 2 3; 5 6 7 10; 8 3 1 20; 1 2 5 8')
print(max_product_path(ex1))
Dealing with Negatives:
Negatives can be treated the way as positives. If within out dp algorithm, we look at the absolute distance between neighbors, all the needs to have to negatives is for the value to be unnegated in the end.
Not sure, but one possibility might be to run the algorithm twice. Once, as we've done now, and a second time around that uses absolute value. Select the matrix that returns the maximum value on the bottom row.
Last modified 4yr ago