CODEWITHSUNDEEP
python
Said Yeginoglu
Said Yeginoglu

Reputation: 3

Highest Sum Path in a nxn matrix from origin(0,0) to (n,n)

I have been trying to find a solution to the following question: There is a matrix given of size nxn. You start from (0,0) and want to reach (n,n). You are only allowed to step upwards and to the right (not down or to the left). What is the maximal sum that can be gained this way, and through which path?

I could find the highest sum but not the path in my code. Please give me a hand guys :)

# Forming a matrix
mat=[[0,0,20,4],
     [4,5,3,6],
     [1,3,5,2],
     [50,4,6,0]]

def maxPath(matrix):
    # Determine the size of the matrix
    m=3;
    n=3;
    
    # Giving all the cells max value as '0' for a start 
    maxPath=[[0 for x in range(n+1)]for y in range(m+1)]
    
    #Giving the first start cell max value as it's own value
    maxPath[0][0]=matrix[0][0]
    
    
    # Calcuating max-sum for each cell in the first column
    for i in range (1,m+1):
        below = maxPath[i-1][0]
        maxPath[i][0] = below + matrix[i][0]
    
    # Calcuating max-sum for each cell in the first row
    for j in range (1,n+1):
        left = maxPath[0][j-1]
        maxPath[0][j] = left + matrix[0][j]   
    
    # Calcuating max-sum for each cell for the rest of the grid
    for i in range (1,m+1):
        for j in range (1,n+1):
            left = maxPath[i-1][j]
            below = maxPath[i][j-1]  
            maxPath[i][j] = matrix[i][j] + max(left, below)
    return maxPath[m][n]

highestSumPath = maxPath(mat)
print("Highest-sum is: ",highestSumPath)

Upvotes: 0

Views: 215

Answers (1)

wtw
wtw

Reputation: 688

It's possibly easiest to keep track of the your path while you're filling in maxPath. You haven't said how you want to store the path, so I'm going to assume that a list of the cell coordinates in order will get you started. For example:

path = [(0, 0), (0, 1), (1, 1)]  # start at (0, 0) and go to (0, 1) then (1, 1)

Just like you build up maxPath by adding values from matrix, you build the path to any cell by "adding" (putting onto the end of the list) the cell's coordinates to path to the previous cell.

def maxPath(matrix):
    # Determine the size of the matrix
    m=3;
    n=3;
    
    # Giving all the cells max value as '0' for a start 
    maxPath=[[0 for x in range(n+1)]for y in range(m+1)]
    
    # An array to store the path as I find it
    path = [[None for x in range(n+1)]for y in range(m+1)]
    
    #Giving the first start cell max value as it's own value
    maxPath[0][0]=matrix[0][0]
    path[0][0] = [(0,0)]  # The route to the first cell is simply (0, 0)
    
    # Calcuating max-sum for each cell in the first column
    for i in range (1,m+1):
        below = maxPath[i-1][0]
        maxPath[i][0] = below + matrix[i][0]
        
        # the path to cell [i][0] is the path to cell [i-1][0] followed by (i, j)
        # copy that path, then add an extra element for (i,0)
        path[i][0] = list(path[i-1][0]) + [(i,0)]
    
    # Calcuating max-sum for each cell in the first row
    for j in range (1,n+1):
        left = maxPath[0][j-1]
        maxPath[0][j] = left + matrix[0][j]  
        path[0][j] = list(path[0][j-1]) + [(0,j)]
    
    # Calcuating max-sum for each cell for the rest of the grid
    for i in range (1,m+1):
        for j in range (1,n+1):
            left = maxPath[i-1][j]
            below = maxPath[i][j-1]  
            
            if left > below:
                maxPath[i][j] = matrix[i][j] + left
                path[i][j] = list(path[i-1][j]) + [(i,j)]
            else:
                maxPath[i][j] = matrix[i][j] + below
                path[i][j] = list(path[i][j-1]) + [(i,j)]
    
    return maxPath[m][n], path[m][n]

highestSumPath, path = maxPath(mat)
print("Highest-sum is: ",highestSumPath)  # Highest-sum is:  65
print("Path taken: ", path)  # Path taken:  [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]

Note, this isn't the best solution for large arrays - it computes the path to every cell in maxPath. This might take up quite a lot of space... You could avoid this by walking backwards through maxPath, working out where you came from at each step from the values of matrix and maxPath below and left of your position, for example. However, this would be quite different to your starting code.

Upvotes: 1

Related Questions