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.