Company: Agoda
Difficulty: medium
Max Path Sum There is a puzzle using a rectangular grid. The upper left corner is at (row, column) = (0, 0). Each cell contains an integer. The score starts at 0 and is the sum of all the integers in each cell visited in the grid is traversed. Movement begins in either the top or the bottom row and stays within the bounds of the grid. Only 1 cell can be visited per row per direction. Determine the maximum achievable score. Movement Rules: From a cell (i,j) = (0,p), i.e. in the top row: (i+1, j-1) (i+1, j) (i+1, j+1) From a cell (i,j) = (rows-1,q), i.e. in the bottom row: (i-1, j-1) (i-1, j) (i-1, j+1) Function Parameters int board[n][m] : the values for the grid cells p : row 0 starting column q : row n-1 starting column Returns int: the maximum achievable score from the two start positions Constraints 2 ≤ n, m ≤ 501 0 ≤ board[i][j] 0 ≤ p, q ≤ m-1 Example board = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] p = 1 q = 0 Starting at (0,1): 1 2 3 4 5 6 7 8 9 Maximum score is 2+6+9 = 17 Starting at (