# Finding the max product of a 2D array

Given a 2D array of unsigned integers and a maximum length n, find a path in that matrix that is not longer than n and which maximizes the product of the elements in the path. The output should consist of both the path and the product.

A path consists of neighbouring integers that are either all in the same row, or in the same column, or down a diagonal in the down-right direction. The code for this problem is below:

def maxPathProduct(self, matrix, maxLen):
"""
Take a 2D Array of ints
and return the largest Product of list of ints of length maxLen
and the product of the list integers
"""
maxProduct = -1
maxList = []
if len(matrix) == 0:
return maxProduct, maxList
numRows = len(matrix)
numCols = len(matrix[0])

for direction in range(1, 4):
if direction == 1:
numLines = numCols
elif direction == 2:
numLines = numRows
elif direction == 3:
numLines = numRows + numCols -1
for line in range (0,numLines):
pathProduct = 1
pathLen = 0
if direction == 1:
elif direction ==2:
elif direction == 3:
headRow =  0 if line  >= numRows else line
headCol =  line-numRows if line  >= numRows else 0
pathList = []
pathLen+=1
if pathLen > maxLen:
pathProduct /= matrix[tailRow][tailCol]
pathList = pathList[1:]
if direction== 1:
tailRow += 1
elif direction == 2:
tailCol += 1
elif direction == 3:
tailCol += 1
tailRow += 1
if pathProduct > maxProduct:
maxProduct = pathProduct
maxList = pathList
if direction== 1:
elif direction == 2:
elif direction == 3:
return maxProduct, maxList
matrix = [
[1,  2,  3,  4,  5],
[1,  1,  2,  3,  5],
[3,  4,  5,  5,  5],
[3,  4,  5, 9,  5],
[1,  1,  5,  5, 25],
]


The issue here is that the solution constitutes changing the values of the "head" and "tail" variables based on the current direction being considered in the 2D requiring the use of multiple if/else statements. This makes the code a look longer and possibly harder to follow. I'm basing this off of these errors listed by pylint:

[pylint] C0103:Invalid function name "maxPathProduct"
[pylint] R0914:Too many local variables (17/15)
[pylint] C0103:Invalid argument name "maxLen"
[pylint] C0103:Invalid argument name "maxLen"


I'm not sure if these errors actually warrant any changes but if they do, is there anyway to possibly refactor the if/else statements or any unwieldy part of the code while maintaining the functionality of the solution?

First of all, if this function is not in a class you must remove the self parameter, there's no need of that. Then you should insert a check if the parameters are correct, that is the rows number and the columns number must be at least equals to maxLength:

if len(matrix) < maxLen and len(matrix[0]) < maxLen:
return -1 # return error code


In this cases, when you have to move across a matrix, I suggest you to use a sort of direction tuples, which are tuples of the form (1,0), (0,1), (1,1), (-1,0) etc..; so for each element of the matrix you add to the indexes of that element one of this tuples multiplied for a number. Maybe it's more complicate to speak about it than show it:

def maxPathProduct(matrix, maxLen):
if len(matrix) < maxLen and len(matrix[0]) < maxLen:
return -1
maxProduct = -1
maxList = []
directions = [(1, 0), (0, 1), (1, 1)]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
for dir in directions:
tempProduct = 1
tempList = []
inc = 0
indexOutOfBound = False
while len(tempList) < maxLen and not indexOutOfBound:
row = i + dir[0] * inc
col = j + dir[1] * inc
if row < len(matrix) and col < len(matrix[0]):
tempProduct *= matrix[row][col]
tempList.append(matrix[row][col])
inc += 1
else:
indexOutOfBound = True
if tempProduct > maxProduct:
maxProduct = tempProduct
maxList = tempList
return maxProduct, maxList


In this case you have only to move from left-to-right ((0,1)), up-to-down ((1,0)) and diagonally-up-to-down ((1,1)). With those direction tuples you can avoid that terrible long list of if-elif-else. I've tried this solution a bit, I'm not completely sure that it works, but I hope that you understand the trick.

• As a slight optimization: they're unsigned integers, that means the tuple giving the max product is the same as the one give the max sum. But sum is usually faster than multiplication and takes longer to get to an overflow, so you could check the sum instead of the product. – ChatterOne Mar 21 '17 at 22:46