Collect the Most Rocks with Upward and Rightward Moves
Company: Goldman Sachs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Overview: Maximize rocks collected from the bottom-left to the top-right of a grid using only upward and rightward moves.
Constraints
- rocks is a nonempty rectangular integer matrix with 1 through 200 rows and 1 through 200 columns.
- Every cell contains 0 through 1000000 rocks.
- Row 0 is the top row. Start at bottom-left and finish at top-right. Move one cell up or right at each step.
- There are no blocked cells. Include both endpoints; return only the maximum total.
Examples
Input: ([[1, 2, 3], [4, 5, 6]],)
Expected Output: 18
Explanation: Published sample 1: bottom row then upward gives 4+5+6+3=18.
Input: ([[5], [0], [7]],)
Expected Output: 12
Explanation: Published sample 2: the sole path totals 7+0+5=12.