title: Maximum sum path in the matrix with a given starting point
body: <p>I am learning to tackle a similar type of dynamic programming problem to find a maximum path sum in a matrix.</p>
  <p>I have based my learning on this algorithm on the website below.</p>
  <p>Source: <a href="https://www.geeksforgeeks.org/maximum-path-sum-matrix/" rel="nofollow noreferrer">Maximum path sum in matrix</a></p>
  <p>The problem I am trying to solve is a little bit different from the one on the website.</p>
  <p>The algorithm from the website makes use of <code>max()</code> to update values in the matrix to find max values to create a max path.</p>
  <p>For example, given an array:</p>
  <pre><code>sample = [[110, 111, 108, 1],
            [9, 8, 7, 2],
            [4, 5, 10, 300],
            [1, 2, 3, 4]]
  </code></pre>
  <p>The best sum path is  111 + 7 + 300 + 4 = <strong>422</strong></p>
  <p>In the example above, the algorithm finds the first path by finding what is the max value of the first row of the matrix.</p>
  <p>My question is, what if have to specify the starting point of the algorithm. The value h is given as the first element to start.</p>
  <p>For example, given the sample array above, if h = 0, we need to start at sample[0][h], therefore the best path would be</p>
  <p>110 (Our staring point) + 8 + 10 + 4 = 132</p>
  <p>As you can see, the path can only travel downwards or adjacent, therefore if we start at h = 0, there will be values that we cannot reach some values such as 300.</p>
  <p>Here is my messy attempt of solving this within the O(N*D) complexity,</p>
  <pre><code># Find max path given h as a starting point
  def find_max_path_w_start(mat, h):
      res = mat[0][0]
      M = len(mat[0])
      N = len((mat))
  
      for i in range(1, N):
          res = 0
          for j in range(M):
              # Compute the ajacent sum of the ajacent values from h
              if i == 1:
                  # If h is starting area, then compute the sum, find the max
                  if j == h:
                      # All possible
                      if (h &gt; 0 and h &lt; M - 1):
                          mat[1][h + 1] += mat[0][h]
                          mat[1][h] += mat[0][h]
                          mat[1][h - 1] += mat[0][h]
                          print(mat)
                      # Diagona Right not possible
                      elif (h &gt; 0):
                          mat[1][h] += mat[0][h]
                          mat[1][h - 1] += mat[0][h]
                      # Diagonal left not possible
                      elif (h &lt; M - 1):
                          mat[1][h] += mat[0][h]
                          mat[1][h + 1] += mat[0][h]
                  # Ignore value that has been filled.
                  elif j == h + 1 or j == h - 1 :
                      pass
                  # Other elements that cannot reach, make it -1
                  elif j &gt; h + 1 or j &lt; h - 1:
                      mat[i][j] = -1
              else:
                  # Other elements that cannot reach, make it -1
                  if j &gt; h + 1 or j &lt; h - 1:
                      mat[i][j] = -1
                  else:
                      # When all paths are possible
                      if (j &gt; 0 and j &lt; M - 1):
                          mat[i][j] += max(mat[i - 1][j],
                                           max(mat[i - 1][j - 1],
                                               mat[i - 1][j + 1]))
                      # When diagonal right is not possible
                      elif (j &gt; 0):
                          mat[i][j] += max(mat[i - 1][j],
                                           mat[i - 1][j - 1])
                      # When diagonal left is not possible
                      elif (j &lt; M - 1):
                          mat[i][j] += max(mat[i - 1][j],
                                           mat[i - 1][j + 1])
  
              res = max(mat[i][j], res)
  
      return res
  </code></pre>
  <p>My approach is to only store the reachable values, if example if we start at h = 0, since we are starting at <code>mat[0][h]</code>, we can only compute the <strong>sum of current and bottom</strong> <code>max(mat[1][h]</code> and <strong>sum of current and adjacent right</strong> <code>mat[1][h + 1])</code>, for other values I mark it as -1 to mark it as unreachable.</p>
  <p>This doesn't return the expected sum at the end.</p>
  <p>Is my logic incorrect? Are there other values that I need to store to complete this?</p>