Maximum Number of Points with Cost — LeetCode 1937 Python Solution

The problem

You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix.

Example

Input

points = [[1,2,3],[1,5,1],[3,1,1]]

Output

9

Explanation

The blue cells denote the optimal cells to pick, which have coordinates (0, 2), (1, 1), and (2, 0).

Python solution

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points[0])
        f = points[0][:]
        for p in points[1:]:
            g = [0] * n
            lmx = -inf
            for j in range(n):
                lmx = max(lmx, f[j] + j)
                g[j] = max(g[j], p[j] + lmx - j)
            rmx = -inf
            for j in range(n - 1, -1, -1):
                rmx = max(rmx, f[j] - j)
                g[j] = max(g[j], p[j] + rmx + j)
            f = g
        return max(f)

Complexity

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1937. Maximum Number of Points with Cost is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems