# Maximum Number of Points with Cost
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-points-with-cost)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-points-with-cost
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-number-of-points-with-cost/image0.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-number-of-points-with-cost/image1.png) 

**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 <= 105`
* `1 <= m * n <= 105`
* `0 <= points[r][c] <= 105`

# Approaches
## Brute-Force Dynamic Programming
This approach uses dynamic programming to solve the problem. We define `dp[i][j]` as the maximum score we can obtain by picking cells up to row `i`, with the cell in row `i` being at column `j`. 

The base case is the first row, where the score is simply the value of the cell, as there's no preceding row to calculate a penalty from. For any other cell `(i, j)`, we calculate its maximum possible score by considering all possible cells `(i-1, k)` in the previous row. We take the maximum score from the previous row, `dp[i-1][k]`, add the current cell's points, `points[i][j]`, and subtract the penalty `abs(j - k)`. We iterate through all possible `k` to find the maximum achievable score for `dp[i][j]`. The final answer is the maximum value in the last row of our DP table.
**Time:** O(m * n^2) - We iterate through each cell of the `m x n` matrix. For each cell `(i, j)`, we iterate through all `n` columns of the previous row to find the optimal path. This results in three nested loops. · **Space:** O(m * n) - We use a 2D DP table of size `m x n`. This can be optimized to `O(n)` by noticing that for row `i`, we only need the results from row `i-1`.
**Pros:** It is a direct translation of the problem statement into a DP recurrence, making it easy to understand and implement.
**Cons:** The time complexity of `O(m * n^2)` is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The core of this method is a straightforward implementation of the dynamic programming recurrence. We build a `dp` table of the same dimensions as the `points` matrix.

-   **State:** `dp[i][j]` represents the maximum points accumulated up to row `i`, with the path ending at column `j`.
-   **Base Case:** The first row of the `dp` table is initialized directly from the input matrix, as there are no prior rows to consider for penalties: `dp[0][j] = points[0][j]`.
-   **Recurrence:** For every cell `(i, j)` where `i > 0`, we compute `dp[i][j]` by iterating through all possible columns `k` in the previous row `i-1`. For each `k`, we calculate a potential score `dp[i-1][k] - abs(j - k)` and find the maximum among them. This maximum value is then added to `points[i][j]` to get `dp[i][j]`. This requires a nested loop inside the main loops that iterate through rows and columns.

```java
public long maxPoints(int[][] points) {
    int m = points.length;
    int n = points[0].length;

    long[][] dp = new long[m][n];

    // Initialize the first row
    for (int j = 0; j < n; j++) {
        dp[0][j] = points[0][j];
    }

    // Fill the rest of the DP table
    for (int i = 1; i < m; i++) {
        for (int j = 0; j < n; j++) {
            long maxPrev = 0;
            for (int k = 0; k < n; k++) {
                maxPrev = Math.max(maxPrev, dp[i - 1][k] - Math.abs(j - k));
            }
            dp[i][j] = points[i][j] + maxPrev;
        }
    }

    // Find the maximum score in the last row
    long maxScore = 0;
    for (int j = 0; j < n; j++) {
        maxScore = Math.max(maxScore, dp[m - 1][j]);
    }

    return maxScore;
}
```
Note: The space complexity can be optimized to `O(n)` by only storing the DP values for the previous row, but the time complexity remains the bottleneck.
### Algorithm
1.  Define a 2D DP array `dp[m][n]`, where `dp[i][j]` stores the maximum score achievable up to row `i`, ending at column `j`.
2.  **Base Case:** For the first row (`i=0`), there is no previous row, so the score is just the points in that cell. Initialize `dp[0][j] = points[0][j]` for all `j` from `0` to `n-1`.
3.  **Transition:** For each subsequent row `i` (from `1` to `m-1`) and each column `j` (from `0` to `n-1`), calculate `dp[i][j]`.
    -   To find the score for `dp[i][j]`, we must have come from some cell `(i-1, k)` in the previous row.
    -   The score contribution from the previous rows ending at `(i-1, k)` is `dp[i-1][k]`. 
    -   The cost of moving from column `k` to `j` is `abs(j - k)`.
    -   So, the total score is `dp[i-1][k] + points[i][j] - abs(j - k)`.
    -   We need to maximize this over all possible previous columns `k`.
    -   The recurrence relation is: `dp[i][j] = points[i][j] + max(dp[i-1][k] - abs(j - k))` for `0 <= k < n`.
4.  **Final Answer:** After filling the entire `dp` table, the maximum score is the maximum value in the last row, `max(dp[m-1][j])` for `0 <= j < n`.

## Optimized Dynamic Programming
The `O(m * n^2)` complexity of the brute-force approach comes from the inner loop that recalculates the maximum previous score for every cell. We can optimize this by observing that the calculation `max_{k}(dp[k] - abs(j-k))` can be broken down. The `abs(j-k)` term depends on whether `k <= j` or `k > j`. This structure allows us to precompute the necessary maximums for each row in linear time.

For each row, we can use two passes. A left-to-right pass calculates the maximum score coming from a previous cell `k` where `k <= j`. A right-to-left pass does the same for `k >= j`. By combining the results of these two passes, we can find the optimal previous cell for each current cell `j` in `O(1)` time. This reduces the complexity of processing each row from `O(n^2)` to `O(n)`, leading to an overall time complexity of `O(m * n)`.
**Time:** O(m * n) - For each of the `m` rows, we perform a constant number of passes (three) over the `n` columns. This results in a linear time complexity with respect to the size of the input matrix. · **Space:** O(n) - We use a 1D `dp` array of size `n` to store the results for the current row, and two additional arrays `left` and `right` of size `n` for the intermediate calculations.
**Pros:** Highly efficient with a time complexity of `O(m * n)`, which passes the given constraints.; Space-efficient, using only `O(n)` extra space.
**Cons:** The logic is more complex than the brute-force approach, involving multiple passes and auxiliary arrays for each row's computation.
### Explanation
This optimized DP approach avoids the costly inner loop by using a more clever way to compute the maximum score from the previous row. We maintain a 1D array, `dp`, representing the maximum scores for the most recently processed row.

For each new row `i`, we want to compute a new `dp` array. The value for `dp[j]` will be `points[i][j] + max_prev_score`, where `max_prev_score = max_{0 <= k < n} (old_dp[k] - abs(j - k))`. 

We can find `max_prev_score` efficiently. Let's analyze the term `old_dp[k] - abs(j-k)`:
- If `k <= j`, it's `old_dp[k] - (j-k) = old_dp[k] + k - j`.
- If `k > j`, it's `old_dp[k] - (k-j) = old_dp[k] - k + j`.

So, `max_prev_score` is `max( max_{k<=j}(old_dp[k]+k) - j, max_{k>j}(old_dp[k]-k) + j )`.

Instead of recomputing these maximums every time, we can use two passes over the `old_dp` array:
1.  A left-to-right pass to compute `max_{k<=j}(old_dp[k] - (j-k))` for all `j`.
2.  A right-to-left pass to compute `max_{k>=j}(old_dp[k] - (k-j))` for all `j`.

Let `left[j] = max_{k<=j}(old_dp[k] - (j-k))` and `right[j] = max_{k>=j}(old_dp[k] - (k-j))`. These can be computed via simple recurrences:
- `left[j] = max(left[j-1] - 1, old_dp[j])`
- `right[j] = max(right[j+1] - 1, old_dp[j])`

After computing the `left` and `right` arrays, the new `dp[j]` is `points[i][j] + max(left[j], right[j])`. Since the total score can exceed the capacity of a 32-bit integer, we use `long` for our DP arrays.

```java
public long maxPoints(int[][] points) {
    int m = points.length;
    int n = points[0].length;

    long[] dp = new long[n];
    for (int j = 0; j < n; j++) {
        dp[j] = points[0][j];
    }

    for (int i = 1; i < m; i++) {
        long[] left = new long[n];
        left[0] = dp[0];
        for (int j = 1; j < n; j++) {
            left[j] = Math.max(left[j - 1] - 1, dp[j]);
        }

        long[] right = new long[n];
        right[n - 1] = dp[n - 1];
        for (int j = n - 2; j >= 0; j--) {
            right[j] = Math.max(right[j + 1] - 1, dp[j]);
        }

        for (int j = 0; j < n; j++) {
            dp[j] = points[i][j] + Math.max(left[j], right[j]);
        }
    }

    long maxScore = 0;
    for (long score : dp) {
        maxScore = Math.max(maxScore, score);
    }

    return maxScore;
}
```
### Algorithm
1.  Since computing row `i` only depends on row `i-1`, we can optimize space by using a 1D array, `dp`, of size `n` to store the results of the previous row.
2.  Initialize `dp` with the values from the first row of `points`.
3.  Iterate through the rows of `points` from `i = 1` to `m-1`.
4.  For each row `i`, we calculate the new `dp` values. The key is to optimize the calculation of `max_{k}(dp[k] - abs(j-k))`. This can be done in two passes for each row.
5.  **Pass 1 (Left-to-Right):**
    -   Create a temporary array `left` of size `n`.
    -   `left[j]` will store `max_{k<=j}(dp[k] - (j-k))`. This can be calculated with the recurrence `left[j] = max(left[j-1] - 1, dp[j])`.
    -   Initialize `left[0] = dp[0]` and iterate from `j=1` to `n-1`.
6.  **Pass 2 (Right-to-Left):**
    -   Create a temporary array `right` of size `n`.
    -   `right[j]` will store `max_{k>=j}(dp[k] - (k-j))`. This can be calculated with the recurrence `right[j] = max(right[j+1] - 1, dp[j])`.
    -   Initialize `right[n-1] = dp[n-1]` and iterate from `j=n-2` down to `0`.
7.  **Update DP array:**
    -   For each column `j`, the maximum value from the previous row is `max(left[j], right[j])`.
    -   Update `dp[j] = points[i][j] + max(left[j], right[j])`.
8.  After iterating through all rows, the maximum value in the final `dp` array is the answer.

# Solutions
### Java

```java
class Solution {
public
  long maxPoints(int[][] points) {
    int n = points[0].length;
    long[] f = new long[n];
    final long inf = 1L << 60;
    for (int[] p : points) {
      long[] g = new long[n];
      long lmx = -inf, rmx = -inf;
      for (int j = 0; j < n; ++j) {
        lmx = Math.max(lmx, f[j] + j);
        g[j] = Math.max(g[j], p[j] + lmx - j);
      }
      for (int j = n - 1; j >= 0; --j) {
        rmx = Math.max(rmx, f[j] - j);
        g[j] = Math.max(g[j], p[j] + rmx + j);
      }
      f = g;
    }
    long ans = 0;
    for (long x : f) {
      ans = Math.max(ans, x);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maxPoints(vector<vector<int>> &points) {
    using ll = long long;
    int n = points[0].size();
    vector<ll> f(n);
    const ll inf = 1e18;
    for (auto &p : points) {
      vector<ll> g(n);
      ll lmx = -inf, rmx = -inf;
      for (int j = 0; j < n; ++j) {
        lmx = max(lmx, f[j] + j);
        g[j] = max(g[j], p[j] + lmx - j);
      }
      for (int j = n - 1; ~j; --j) {
        rmx = max(rmx, f[j] - j);
        g[j] = max(g[j], p[j] + rmx + j);
      }
      f = move(g);
    }
    return *max_element(f.begin(), f.end());
  }
};

```

### Python

```python
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int: n = len(points[0]) f = points[0][:] for p in points[1:]: g = [0] * n lmx = - inf for j in range(n): lmx = max(lmx, f[j] + j) g[j] = max(g[j], p[j] + lmx - j) rmx = - inf for j in range(n - 1, - 1, - 1): rmx = max(rmx, f[j] - j) g[j] = max(g[j], p[j] + rmx + j) f = g return max(f)

```