> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/recursion-and-dynamic-programming/maximum-product-in-matrix.md).

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

![](/files/-LoJIq4cJuS3MP--BmZ2)

**Complexity:** O(n\*m) time and space

```python
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.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/recursion-and-dynamic-programming/maximum-product-in-matrix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.