You are given an m x n integer matrix grid.
Two players move across the grid:
(0, 0) and can move only right or down. Their destination is the bottom-right cell (m - 1, n - 1).(m - 1, 0) and can move only right or up. Their destination is the top-right cell (0, n - 1).Each player must choose a valid path from their respective starting cell to their destination.
A cell is called shared if it belongs to both chosen paths.
Return an integer denoting the maximum possible sum of values of all shared cells.
Example 1:
Input: grid = [[1,2,0,-3],[1,-2,1,0],[-4,2,-1,3],[3,-3,3,-2],[-1,-5,0,1]]
Output: 4
Explanation:
The diagram shows one optimal choice of paths.(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (2, 3) → (3, 3) → (4, 3)(4, 0) → (4, 1) → (3, 1) → (2, 1) → (2, 2) → (2, 3) → (1, 3) → (0, 3)(2, 1), (2, 2), and (2, 3).2 + (-1) + 3 = 4, which is the maximum possible sum.Example 2:
Input: grid = [[4,-2,-3],[-1,-3,-1],[-4,2,-1]]
Output: 3
Explanation:
One optimal pair of paths is shown in the diagram.
(0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2)(2, 0) → (1, 0) → (0, 0) → (0, 1) → (0, 2)(0, 0) and (1, 0).4 + (-1) = 3, which is the maximum possible.Constraints:
m == grid.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 5 * 105-100 <= grid[i][j] <= 100Loading editor...
[[1,2,0,-3],[1,-2,1,0],[-4,2,-1,3],[3,-3,3,-2],[-1,-5,0,1]]