Find max path sum

max_path_sum_game.py

# Complete the 'maxPathSum' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. 2D_INTEGER_ARRAY board
#  2. INTEGER p
#  3. INTEGER q

# NOTE use a dict to cache the results ro improve performance.

def maxPathSum(board, p, q):
  # Write your code here

  n = len(board)
  m = len(board[0])

  return max(
      max_top_down(board, 0, p, m, n),
      max_bottom_up(board, n-1, q, m, n)
  )

def max_top_down(board, i, p, m, n):
  # base case
  if i == n-1:
    b1 = board[i][p-1] if p > 0 else 0
    b2 = board[i][p]
    b3 = board[i][p+1] if p < m-1 else 0
    return max(b1, b2, b3)

  m1 = board[i][p] + max_top_down(board, i+1, p-1, m, n) if p > 0 else 0
  m2 = board[i][p] + max_top_down(board, i+1, p, m, n)
  m3 = board[i][p] + max_top_down(board, i+1, p+1, m, n) if p < m-1 else 0
  return max(m1, m2, m3)

def max_bottom_up(board, i, q, m, n):
  # base case
  if i == 0:
    b1 = board[i][q-1] if q > 0 else 0
    b2 = board[i][q]
    b3 = board[i][q+1] if q < m-1 else 0
    return max(b1, b2, b3)

  m1 = board[i][q] + max_bottom_up(board, i-1, q-1, m, n) if q > 0 else 0
  m2 = board[i][q] + max_bottom_up(board, i-1, q, m, n)
  m3 = board[i][q] + max_bottom_up(board, i-1, q+1, m, n) if p < m-1 else 0
  return max(m1, m2, m3)