AlgoMaster Logo

Maximum Number of Points with Cost

Last Updated: March 28, 2026

medium
5 min read

Understanding the Problem

We have a grid of points and need to pick exactly one cell from each row to maximize our total score. The catch is that switching columns between rows costs us. If we pick column c1 in row r and column c2 in row r+1, we pay a penalty of |c1 - c2|. So staying in the same column is free, but drifting sideways costs more the further we move.

This is essentially a path problem through the grid, where we move from row to row, choosing one column per row, and the "travel cost" between rows is the absolute difference of column indices. We want to maximize the sum of cell values minus the total travel cost.

The key observation is that each row's optimal choices depend only on the previous row's results, not on the entire history. This makes it a natural fit for dynamic programming where we build up the answer row by row.

Key Constraints:

  • 1 <= m, n <= 10^5 --> Both the number of rows and columns can be very large individually.
  • 1 <= m * n <= 10^5 --> But the total number of cells is at most 100,000. This means if we have many rows, we have few columns, and vice versa. This is an important detail.
  • 0 <= points[r][c] <= 10^5 --> All values are non-negative, so we always want to pick the highest value cells if the cost allows it.

Approach 1: Brute Force DP

Intuition

The most natural way to think about this is row by row. After processing row r, we know the best possible score ending at each column. To compute the best score for column c in row r+1, we consider every column j in row r, take dp[j] - |j - c| + points[r+1][c], and pick the maximum.

This is a straightforward 2D DP where dp[c] represents the maximum score achievable if we pick column c in the current row. For each new row, we compute new DP values by checking all possible previous columns.

Algorithm

  1. Initialize dp[c] = points[0][c] for all columns in the first row.
  2. For each subsequent row r from 1 to m-1:
    • Create a new array newDp of size n.
    • For each column c in row r, compute newDp[c] = max(dp[j] - |j - c|) + points[r][c] over all columns j.
    • Set dp = newDp.
  3. Return the maximum value in dp.

Example Walkthrough

1Initialize: pick values from row 0 as starting dp
0
1
2
0
1
2
3
1
1
5
1
2
3
1
1
1/8

Code

The transition formula dp[j] - |j - c| has structure we are not exploiting. What if we split the absolute value into two cases and precomputed the best value from the left and right in linear passes?

Approach 2: Optimized DP with Left-Right Decomposition

Intuition

The bottleneck in the brute force is computing max(dp[j] - |j - c|) for every column c. Let's break the absolute value into two cases:

  • When j <= c: |j - c| = c - j, so the term becomes dp[j] + j - c. To maximize this, we want max(dp[j] + j) over all j <= c, and then subtract c.
  • When j >= c: |j - c| = j - c, so the term becomes dp[j] - j + c. To maximize this, we want max(dp[j] - j) over all j >= c, and then add c.

Here is the key insight: max(dp[j] + j) for j <= c is a prefix maximum, and max(dp[j] - j) for j >= c is a suffix maximum. Both can be computed in a single linear pass. So instead of an O(n) inner loop for each column, we do two O(n) preprocessing passes and combine them in O(1) per column.

Algorithm

  1. Initialize dp[c] = points[0][c] for all columns in the first row.
  2. For each subsequent row r from 1 to m-1:
    • Build a left array where left[c] = max(dp[j] + j) for all j from 0 to c. Scan left to right, keeping a running maximum.
    • Build a right array where right[c] = max(dp[j] - j) for all j from c to n-1. Scan right to left, keeping a running maximum.
    • For each column c, compute newDp[c] = max(left[c] - c, right[c] + c) + points[r][c].
    • Set dp = newDp.
  3. Return the maximum value in dp.

Example Walkthrough

1dp initialized from row 0: [1, 2, 3]
0
1
1
2
2
3
1/8

Code

The time is now optimal, but we are allocating three extra arrays per row. Can we fold the left and right passes directly into the dp array to avoid the extra allocations?

Approach 3: Space-Optimized DP (In-Place)

Intuition

We can eliminate the separate left and right arrays by folding the two passes directly into the dp update. The left-to-right pass propagates the best values rightward (each step decays by 1), and the right-to-left pass propagates leftward. After both passes, each dp[c] holds exactly max over all j of (old_dp[j] - |j - c|). Then we add the current row's points.

Algorithm

  1. Initialize dp[c] = points[0][c] for all columns.
  2. For each subsequent row r:
    • Left pass: scan c from 1 to n-1, setting dp[c] = max(dp[c], dp[c-1] - 1).
    • Right pass: scan c from n-2 to 0, setting dp[c] = max(dp[c], dp[c+1] - 1).
    • Add points: for each column c, set dp[c] += points[r][c].
  3. Return the maximum value in dp.

Example Walkthrough

1dp initialized from row 0: [1, 2, 3]
0
1
1
2
2
3
1/8

Code