3148. 矩阵中的最大得分（Rating 1819）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

3148. 矩阵中的最大得分

Rating 1819

思路

脑筋急转弯：需要想清楚一个非常重要结论

从左上某个位置A，经过一系列位置到达右下某个位置B时，得分仅与A和B两个位置的值有关，与路径中的值都无关。

因为

(c1 - c0) + (c2 - c1) + (c3 - c2) + … + (cn - cn-1) = cn - c0

因此，对于每个位置，我们找到其左上最小的值（不包含自己）即可算出以这个位置为终点的得分

遍历所有位置取最大得分即可

而某个位置左上最小的值可以用二维前缀和的思路维护。

代码

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        premin = [[inf for _ in range(n + 1)] for _ in range(m + 1)] # 二维前缀最小值
        ret = -inf
        for i in range(m):
            for j in range(n):
                mn = min(premin[i + 1][j], premin[i][j + 1]) # 找到左上最小值（不包含自己）
                premin[i + 1][j + 1] = min(grid[i][j], mn) # 更新二维前缀最小值
                ret = max(ret, grid[i][j] - mn) # 更新最大得分
        return ret