LC-1937 Medium LeetCode

1937. Maximum Number of Points with Cost

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 42% Topics: Array, Dynamic Programming, Matrix

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Math & Geometry 12 min

Reference solution (spoiler · python)

# Time:  O(m * n)
# Space: O(n)

class Solution(object):
    def maxPoints(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        dp = points[0]
        for i in xrange(1, len(points)):
            prefix = [0]*len(points[i])
            prefix[0] = dp[0]
            for j in xrange(1, len(points[i])):
                prefix[j] = max(prefix[j-1], dp[j]+j)
            suffix = [0]*len(points[i])
            suffix[-1] = dp[-1]-(len(points[i])-1)
            for j in reversed(xrange(len(points[i])-1)):
                suffix[j] = max(suffix[j+1], dp[j]-j)
            new_dp = [0]*len(points[i])
            for j in xrange(len(points[i])):
                new_dp[j] = max(prefix[j]-j, suffix[j]+j)+points[i][j]
            dp = new_dp
        return max(dp)

Solution from kamyu104/LeetCode-Solutions · MIT