<p>You are given an <code>m x n</code> matrix <code>grid</code> consisting of <strong>positive</strong> integers. You can move from a cell in the matrix to <strong>any</strong> other cell that is either to the bottom or to the right (not necessarily adjacent). The score of a move from a cell with the value <code>c1</code> to a cell with the value <code>c2</code> is <code>c2 - c1</code>.<!-- notionvc: 8819ca04-8606-4ecf-815b-fb77bc63b851 --></p>

<p>You can start at <strong>any</strong> cell, and you have to make <strong>at least</strong> one move.</p>

<p>Return the <strong>maximum</strong> total score you can achieve.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/03/14/grid1.png" style="width: 240px; height: 240px;" />
<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">9</span></p>

<p><strong>Explanation:</strong> We start at the cell <code>(0, 1)</code>, and we perform the following moves:<br />
- Move from the cell <code>(0, 1)</code> to <code>(2, 1)</code> with a score of <code>7 - 5 = 2</code>.<br />
- Move from the cell <code>(2, 1)</code> to <code>(2, 2)</code> with a score of <code>14 - 7 = 7</code>.<br />
The total score is <code>2 + 7 = 9</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/04/08/moregridsdrawio-1.png" style="width: 180px; height: 116px;" /></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[4,3,2],[3,2,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>

<p><strong>Explanation:</strong> We start at the cell <code>(0, 0)</code>, and we perform one move: <code>(0, 0)</code> to <code>(0, 1)</code>. The score is <code>3 - 4 = -1</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>2 &lt;= m, n &lt;= 1000</code></li>
	<li><code>4 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[-1])

        prefix_down = [[0 for i in range(m)] for i in range(n)]
        prefix_right = [[0 for i in range(m)] for i in range(n)]

        for i in range(n):
            prefix_right[i][m-1] = grid[i][m-1]
            for j in range(m-2,-1,-1):
                prefix_right[i][j] = max(prefix_right[i][j + 1], grid[i][j])
        
        for j in range(m):
            prefix_down[n-1][j] = grid[n-1][j]
            for i in range(n-2,-1,-1):
                prefix_down[i][j] = max(prefix_down[i + 1][j], grid[i][j])
        
        dp = [[0 for i in range(m)] for i in range(n)]

        dp[-1][-1] = -float("inf")

        for i in range(n-2,-1,-1):
            dp[i][-1] = prefix_down[i + 1][-1] - grid[i][-1]

        for j in range(m - 2,-1,-1):
            dp[-1][j] = prefix_right[-1][j + 1] - grid[-1][j]
        
        


        for i in range(n-2,-1,-1):
            for j in range(m-2,-1,-1):
                # print(f"{i},{j} = ",
                #     max(dp[i + 1][j],0) + grid[i + 1][j] - grid[i][j], 
                #     max(dp[i][j + 1],0) + grid[i][j + 1] - grid[i][j], 
                #     prefix_down[i + 1][j]  - grid[i][j],
                #     prefix_right[i][j + 1] - grid[i][j]
                # )
                # print(f"{i},{j} = ", dp)
                dp[i][j] = max(
                    max(dp[i + 1][j],0) + grid[i + 1][j] - grid[i][j], 
                    max(dp[i][j + 1],0) + grid[i][j + 1] - grid[i][j], 
                    prefix_down[i + 1][j]  - grid[i][j],
                    prefix_right[i][j + 1] - grid[i][j]
                )
                # print(f"{i},{j} = ", dp)
        # print(dp[2][2])
        ans = -float("inf") 
        # print(dp)
        for row in dp:
            # print(row)
            ans = max(ans, max(row))
        
        return ans
        @cache 
        def dfs(i,j):
            res = -float("inf")

            if i == n - 1 and j == m - 1:
                return 0
            
            for y in range(i + 1,n):
                res = max(res, max(dfs(y,j),0) + grid[y][j] - grid[i][j])
            
            for x in range(j + 1, m):
                res = max(res, max(dfs(i,x),0) + grid[i][x] - grid[i][j])
            
            return res
        
        dfs(0,0)
        ans = -float("inf")
        for i in range(n):
            for j in range(m):
                # print(dfs(i,j), end = " ")
                if i == n - 1 and j == m - 1:
                    continue
                ans = max(ans, dfs(i,j))
            # print()
        return ans
            


        
1456