Collect the Most Rocks with Upward and Rightward Moves

Collect the Most Rocks

You are given an m x n 2D integer array grid, where grid[r][c] represents the number of rocks present at coordinate (r, c).

You start at the bottom-left corner of the grid (m - 1, 0) and must reach the top-right corner (0, n - 1). At each step, you can only move:

• Up: from (r, c) to (r - 1, c)
• Right: from (r, c) to (r, c + 1)

When you visit a cell, you collect all the rocks located in that cell. Return the maximum total number of rocks you can collect.

Function Signature

def max_rocks(grid: list[list[int]]) -> int:
    pass

Examples

Example 1:

Input: grid = [
  [0, 2, 5],
  [1, 1, 3],
  [2, 1, 1]
]
Output: 12
Explanation: 
Start at (2, 0) with 2 rocks.
Move up to (1, 0) (+1 = 3).
Move right to (1, 1) (+1 = 4).
Move right to (1, 2) (+3 = 7).
Move up to (0, 2) (+5 = 12).
Total rocks collected = 12.

Example 2:

Input: grid = [
  [1, 3],
  [2, 4]
]
Output: 8
Explanation:
Path: (1, 0) -> (1, 1) -> (0, 1)
Rocks: 2 + 4 + 3 = 9
Path: (1, 0) -> (0, 0) -> (0, 1)
Rocks: 2 + 1 + 3 = 6
The maximum is 9.

Constraints

• m == len(grid)
• n == len(grid[0])
• 1 <= m, n <= 1000
• 0 <= grid[r][c] <= 10^5

Edge Cases

• 1 x 1 grid: The answer is simply grid[0][0].
• Single row (m = 1) or single column (n = 1): Only one valid path exists.