Maximum-Sum Path in a Matrix (No Revisits)

Requirements

• Input: an $m \times n$ grid named grid; its values may be below zero. The function signature is max_path_sum(grid: list[list[int]]) -> int.
• Moves are limited to the four orthogonal neighbors: up, down, left, and right.
• Goal: choose a cell path that never uses the same cell twice and has the largest possible total of its cell values. The path may start and end at any cells.

Notes

• Do not mistake this for the standard matrix dynamic-programming exercise that travels from the upper-left corner to the lower-right corner using only right and down moves. That restricted version is polynomial; verify both the allowed moves and the no-revisit rule before coding.