PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Given a 2D array A, find the maximum sum of a path that starts at a cell in the top row and ends at a cell in the bottom row and in each step not moving upwards. Sounds like a DP ( Dynamic Programming ) problem, but the state to be maintained can be tricky. Cells can be visited more than once here and so you need to maintain more additional information in the state than just (curRow, curCol). A situation can be like below,
…L*******D*******S************R…
Starting from S, you move right till R, reverse direction and go left till L, reverse direction again and move right till D and get down there to go to the row below. Thinking of tricky cases like this gives a good understanding of the problem and helps you decide the DP state and check if it fits in time limit or not. The grid size is very huge 2012 x 2012, so we need to optimize the memory used for dp array. Also, using memoization and going very deep in the recursion stack may create overhead. Here is a nice idea to avoid all these things.
We go from bottom to top and at each row we find the array dp[ ] , where dp[i] is the maximum sum of a path if we start the journey from cell i and get down to next row at a cell to the right of i. So the optimum path traverses some cells in the current row and move down to the next row at cell j > i, i.e., the cell at which we move down is to the right of the cell i. We can first go left and take as much as we can, this is exactly same as the maximum sum of a contiguous subarray ending at index i and then go right i.e., dp[i+1]. A linear traversal from right to left is enough. Similarly we can handle the case when j <= i. Overall complexity is O(RxC). Refer to writer’s code below.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.