Formatted question description: https://leetcode.ca/all/1937.html

# 1937. Maximum Number of Points with Cost

## Level

Medium

## Description

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`

## Solution

Use dynamic programming. Create a 2D array `dp`

of `m`

rows and `n`

columns, where `dp[i][j]`

represents the maximum number of points at position `(i, j)`

. When `i = 0`

, `dp[0][j] = points[0][j]`

for all `0 <= j < n`

.

For `1 <= i < m`

, to calculate `dp[i][j]`

, the maximum values from the previous row need to be calculated. Let `prevRowLeft[j] = dp[i - 1][j] - (n - 1 - j)`

and `prevRowRight[j] = dp[i - 1][j] - j`

. Let `leftMax[j]`

be the maximum from `prevRowLeft[0]`

to `prevRowLeft[j]`

and `rightMax[j]`

be the maximum from `prevRowRight[j]`

to `prevRowRight[n - 1]`

. Then for `dp[i][j]`

, the value is calculated as `Math.max(leftMax[j] + n - 1 - j, rightMax[j] + j) + points[i][j]`

.

Finally, return the maximum value in `dp[m - 1]`

.

```
class Solution {
public long maxPoints(int[][] points) {
int m = points.length, n = points[0].length;
long[][] dp = new long[m][n];
for (int j = 0; j < n; j++)
dp[0][j] = points[0][j];
for (int i = 1; i < m; i++) {
long[] prevRowLeft = new long[n];
System.arraycopy(dp[i - 1], 0, prevRowLeft, 0, n);
for (int j = n - 2; j >= 0; j--)
prevRowLeft[j] -= n - 1 - j;
long[] prevRowRight = new long[n];
System.arraycopy(dp[i - 1], 0, prevRowRight, 0, n);
for (int j = 1; j < n; j++)
prevRowRight[j] -= j;
long[] leftMax = new long[n];
leftMax[0] = prevRowLeft[0];
for (int j = 1; j < n; j++)
leftMax[j] = Math.max(leftMax[j - 1], prevRowLeft[j]);
long[] rightMax = new long[n];
rightMax[n - 1] = prevRowRight[n - 1];
for (int j = n - 2; j >= 0; j--)
rightMax[j] = Math.max(rightMax[j + 1], prevRowRight[j]);
for (int j = 0; j < n; j++) {
long curLeftMax = leftMax[j] + n - 1 - j;
long curRightMax = rightMax[j] + j;
dp[i][j] = Math.max(curLeftMax, curRightMax) + points[i][j];
}
}
long maxScore = 0;
for (int j = 0; j < n; j++)
maxScore = Math.max(maxScore, dp[m - 1][j]);
return maxScore;
}
}
```