aboutsummaryrefslogtreecommitdiff
path: root/max_num_point_cost.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_num_point_cost.py')
-rw-r--r--max_num_point_cost.py52
1 files changed, 52 insertions, 0 deletions
diff --git a/max_num_point_cost.py b/max_num_point_cost.py
new file mode 100644
index 0000000..3e40ba9
--- /dev/null
+++ b/max_num_point_cost.py
@@ -0,0 +1,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]]))