aboutsummaryrefslogtreecommitdiff
path: root/max_num_point_cost.py
blob: 3e40ba93e88beae5d79e891e8eb7b90f8d001b3d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 1937. Maximum Number of Points with Cost

"""
you are given an 'm * n' integer matrix 'points' (0 indexed). starting with 0
points you want to maximise the numbber of points you can get from the
matrix. to gain points, you must pick one cell in each row. picking the cell
at coordinates '(r, c)' will add 'points[r][c]' to your score. however, you
will lose points if you pick a cell too far from the cell that you picked in
the previous row. for every two adjacent rows 'r' and 'r + 1', picking cells
at coordinates '(r, c_1)' and '(r + 1, c_2)' will subtract 'abs(c_1 - c_2)'
from your score. return the maximum number of points you can achieve
"""


class Solution(object):
    def maxPoints(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        m, n = len(points), len(points[0])
        if m == 1:
            return max(points[0])
        if n == 1:
            return sum(sum(x) for x in points)

        def left(arr):
            left = [arr[0]] + [0] * (n - 1)
            for i in range(1, n):
                left[i] = max(left[i - 1] - 1, arr[i])
            return left

        def right(arr):
            right = [0] * (n - 1) + [arr[-1]]
            for i in range(n - 2, -1, -1):
                right[i] = max(right[i + 1] - 1, arr[i])
            return right

        pre = points[0]
        for i in range(m - 1):
            left, right, curr = left(pre), right(pre), [0] * n
            for j in range(n):
                curr[j] = points[i + 1][j] + max(left[j], right[j])
            pre = curr[:]

        return max(pre)


if __name__ == "__main__":
    obj = Solution()
    print(obj.maxPoints(points=[[1, 2, 3], [1, 5, 1], [3, 1, 1]]))
    print(obj.maxPoints(points=[[1, 5], [2, 3], [4, 2]]))