Author: Yash Gulani
Tester: Ishank Bhardwaj
Editorialist: Ishank Bhardwaj
Given a matrix mat with N rows and M columns, find the maximum sum that can be extracted from it, if we traverse a path, starting from mat[i][N], with 1<=i< N, and taking exactly two left turns, and ending at mat[j][N], with i< j <= N.
The problem can be divided into two parts:
Profit earned in going from given cell to the rightmost cell in shape of ‘L’.
Profit earned in coming from rightmost cell to a given cell.
For a matrix “mat” with dimensions NxM,
dp[i][j] represents the maximum sum that can be obtained by traversing a ‘L’ shaped path formed from the coordinates, (i,j), (x,j) and (x,M) where (i=< x< =N) , for the submatrix with top-left corner at i,j and bottom right corner at N,M.
revCum[i][j] represents the sum, mat[i][j]+mat[i][j+1]+mat[i][j+2]…mat[i][M]
dp[i][j] can be calculated as,
dp[i][j] = mat[i][j] + max(dp[i+1][j],revCum[i][j+1])
(Base cases can be handled accordingly)
After the dp and revCum have been calculated, the matrix can then be traversed and answer can be calculated using
Author’s solution can be found here.