1139. Maximum Sum Path in Grid

Given a grid of numbers, find a path from the top-left to the bottom-right that maximizes the sum of numbers along it, moving only right or down. Return that maximum sum. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the maximum path sum.

Examples

Input: {"grid":[[1,3,1],[1,5,1],[4,2,1]]}
Output: 12
Explanation: 1->3->5->2->1 sums to 12.

Input: {"grid":[[1,2],[3,4]]}
Output: 8
Explanation: 1->3->4 or 1->2->4; best is 8.

Input: {"grid":[[9]]}
Output: 9
Explanation: Single cell.

Constraints

• 1<=rows,cols<=200

Asked by