OLDFAR - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Yash Gulani

Tester: Ishank Bhardwaj

Editorialist: Ishank Bhardwaj

DIFFICULTY:

EASY-MEDIUM

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[i][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:

  1. Profit earned in going from given cell to the rightmost cell in shape of ‘L’.

  2. Profit earned in coming from rightmost cell to a given cell.

For a matrix “mat” with dimensions NxM,

  1. 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.

  2. 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
ans=max(ans, revCum[i][j]+dp[i+1][j])

AUTHOR’S SOLUTION:

Author’s solution can be found here.