PROBLEM LINK:
Author: Yash Gulani
Tester: Ishank Bhardwaj
Editorialist: Ishank Bhardwaj
DIFFICULTY:
EASYMEDIUM
PREREQUISITES:
Dynamic Programming
PROBLEM:
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*[N], with 1<=i< N, and taking exactly two left turns, and ending at mat[j][N], with i< j <= N.
EXPLANATION:
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*[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 topleft corner at i,j and bottom right corner at N,M.

revCum*[j] represents the sum, mat*[j]+mat*[j+1]+mat*[j+2]…mat*[M]
dp*[j] can be calculated as,
dp*[j] = mat*[j] + max(dp[i+1][j],revCum*[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
ans=max(ans, revCum*[j]+dp[i+1][j])
AUTHOR’S SOLUTION:
Author’s solution can be found here.