Finding the coordinates of max sum path in matrix

I have this method which returns the max sum of the path from top left to bottom right (can move only to the right or bottom).

def max_path(grid):
 
    N = len(grid)
    M = len(grid[0])
 
    sum = [[0 for i in range(M + 1)] for i in range(N + 1)]
 
    for i in range(1, N + 1):
        for j in range(1, M + 1):
 
            sum[i][j] = (max(sum[i - 1][j], sum[i][j - 1]) + grid[i - 1][j - 1])
            
    return sum[N][M]
 
 
matrix = [[1, 2, 3], [3, 4, 5]]
 
print(max_path(matrix))

output : 1 + 3 + 4 + 5 = 13

But what I want to get is also the coordinates of the points of the path: [(0,0) (1,0) (1,1) (1,2)]

Answer

The variable sum after the nested-for loops (as written in your code) is

[0, 0, 0, 0],
[0, 1, 3, 6],
[0, 4, 8, 13]

You can work out the coordinates of the max sum by having a initial “pointer” at the bottom right corner (i=1, j =2, ignoring the zeros), and comparing the values that is on the top (i=0, i=2) and on the left (i=1, j=1). Since 8 is larger than 6, we move the “pointer” to the left, and now i=1, j=1.

4 is larger than 3, so we move the pointer to 4 (i=1, j=0)

1 is larger than 0, so we move the pointer to 1 (i=0, j=0)

A basic (untested) implementation of the algorithm is as follows:

def max_path(grid):
 
    N = len(grid)
    M = len(grid[0])
 
    sum = [[0 for i in range(M + 1)] for i in range(N + 1)]
 
    for i in range(1, N + 1):
        for j in range(1, M + 1):
 
            sum[i][j] = (max(sum[i - 1][j], sum[i][j - 1]) + grid[i - 1][j - 1])

    j = M
    i = N
  
    path = []
    while i >  0 and j > 0:
      path.append((i-1,j-1))
      if sum[i-1][j] <= sum[i][j-1]:
        j -= 1 
      else:
        i -= 1
      
    path.reverse()
    return sum[N][M],path
matrix = [[1, 2, 3], [3, 4, 5]]
print(max_path(matrix))