AlgoMaster Logo

Maximum Number of Points with Cost

mediumFrequency8 min readUpdated June 23, 2026

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.

Each row's optimal choices depend only on the previous row's results, not on the entire history of which columns we picked earlier. That property is what makes dynamic programming work here: we can carry forward one number per column and build 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

Process the grid row by row. Let dp[c] be the maximum score achievable for a path that picks column c in the current row. After finishing row r, we know the best score ending at each column. To extend into column c of row r+1, we consider every column j from row r, pay the penalty |j - c| for moving sideways, and add the new cell's value: dp[j] - |j - c| + points[r+1][c]. The best of those over all j is the new dp[c].

The values can grow up to m * max_value, which is 10^5 * 10^5 = 10^10, beyond the range of a 32-bit integer. The DP array uses 64-bit values (long) for that reason.

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 O(m * n^2) cost is fatal here. When n is close to 10^5 (and m is small), n^2 alone is 10^10 operations. The next approach removes the inner loop by splitting the absolute value into two directional cases and precomputing each with a single linear scan.

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.

The term dp[j] + j does not depend on c, so max(dp[j] + j) over j <= c is a prefix maximum that grows as c increases. Likewise max(dp[j] - j) over j >= c is a suffix maximum. Each can be built in one linear pass. So instead of an O(n) inner loop per column, we do two O(n) preprocessing passes and combine them in O(1) per column.

Both decomposed terms are correct upper bounds and at least one is tight: for the column j that actually achieves the maximum, either j <= c (counted in the left pass) or j >= c (counted in the right pass), and the case j = c appears in both. Taking the larger of the two recovers exactly max over j of (dp[j] - |j - c|).

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 each row allocates three extra arrays. The next approach folds both passes directly into the dp array, dropping the separate left and right buffers.

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