Leetcode | Maximum Number of Points with Cost | Java

devstromo · devstromo · commit 3f8ff74f03c6 · 2025-04-20T15:09:09.000-03:00
diff --git a/leetcode/src/main/java/com/devstromo/medium/p1937/DESCRIPTION.md b/leetcode/src/main/java/com/devstromo/medium/p1937/DESCRIPTION.md
@@ -0,0 +1,42 @@
+# 1937. Maximum Number of Points with Cost
+
+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.
+
+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 (where `0 <= r < m - 1`), picking cells at coordinates `(r, c1)` and `(r + 1, c2)` will subtract `abs(c1 - c2)` from your score.
+
+Return the maximum number of points you can achieve.
+
+`abs(x)` is defined as:
+
+- `x` for `x >= 0`.
+- `-x` for `x < 0`.
+
+Example 1:
+
+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).
+You add 3 + 5 + 3 = 11 to your score.
+However, you must subtract abs(2 - 1) + abs(1 - 0) = 2 from your score.
+Your final score is 11 - 2 = 9.
+
+Example 2:
+
+Input: points = [[1,5],[2,3],[4,2]]
+Output: 11
+Explanation:
+The blue cells denote the optimal cells to pick, which have coordinates (0, 1), (1, 1), and (2, 0).
+You add 5 + 3 + 4 = 12 to your score.
+However, you must subtract abs(1 - 1) + abs(1 - 0) = 1 from your score.
+Your final score is 12 - 1 = 11.
+
+Constraints:
+
+- `m == points.length`
+- `n == points[r].length`
+- `1 <= m, n <= 10^5`
+- `1 <= m * n <= 10^5`
+- `0 <= points[r][c] <= 10^5`
diff --git a/leetcode/src/main/java/com/devstromo/medium/p1937/Solution.java b/leetcode/src/main/java/com/devstromo/medium/p1937/Solution.java
@@ -0,0 +1,45 @@
+package com.devstromo.medium.p1937;
+
+public class Solution {
+    public long maxPoints(int[][] points) {
+        int m = points.length;
+        int n = points[0].length;
+
+        long[] prev = new long[n];
+        for (int j = 0; j < n; j++) {
+            prev[j] = points[0][j];
+        }
+
+        for (int i = 1; i < m; i++) {
+            long[] left = new long[n];
+            long[] right = new long[n];
+            long[] curr = new long[n];
+
+            // Left to right
+            left[0] = prev[0];
+            for (int j = 1; j < n; j++) {
+                left[j] = Math.max(left[j - 1] - 1, prev[j]);
+            }
+
+            // Right to left
+            right[n - 1] = prev[n - 1];
+            for (int j = n - 2; j >= 0; j--) {
+                right[j] = Math.max(right[j + 1] - 1, prev[j]);
+            }
+
+            // Choose the best from left or right
+            for (int j = 0; j < n; j++) {
+                curr[j] = points[i][j] + Math.max(left[j], right[j]);
+            }
+
+            prev = curr;
+        }
+
+        long max = 0;
+        for (long val : prev) {
+            max = Math.max(max, val);
+        }
+
+        return max;
+    }
+}
diff --git a/leetcode/src/test/java/com/devstromo/medium/p1937/SolutionUnitTest.java b/leetcode/src/test/java/com/devstromo/medium/p1937/SolutionUnitTest.java
@@ -0,0 +1,25 @@
+package com.devstromo.medium.p1937;
+
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SolutionUnitTest {
+    private final Solution solution = new Solution();
+
+    @Test
+    @DisplayName("Test Maximum Number of Points with Cost")
+    void testMaximumNumberOfPointsWithCost() {
+        assertEquals(9, solution.maxPoints(new int[][]{
+                {1, 2, 3},
+                {1, 5, 1},
+                {3, 1, 1}
+        }));
+        assertEquals(11, solution.maxPoints(new int[][]{
+                {1, 5},
+                {2, 3},
+                {4, 2}
+        }));
+    }
+}
