Maximum Number of Points with Cost
Problem
You are given an m × n grid points and you must pick exactly one cell from every row. Your score is the sum of the picked values, but consecutive rows charge a penalty: if you pick column c1 in one row and column c2 in the next, you pay |c1 − c2|. Return the maximum score you can finish with.
points = [[1,2,3],[1,5,1],[3,1,1]]9def max_points(points):
n = len(points[0])
dp = points[0][:]
for row in points[1:]:
left = [0] * n
right = [0] * n
left[0] = dp[0]
for j in range(1, n):
left[j] = max(left[j - 1] - 1, dp[j])
right[n - 1] = dp[n - 1]
for j in range(n - 2, -1, -1):
right[j] = max(right[j + 1] - 1, dp[j])
dp = [row[j] + max(left[j], right[j]) for j in range(n)]
return max(dp)function maxPoints(points) {
const n = points[0].length;
let dp = points[0].slice();
for (let r = 1; r < points.length; r++) {
const left = new Array(n), right = new Array(n);
left[0] = dp[0];
for (let j = 1; j < n; j++) left[j] = Math.max(left[j - 1] - 1, dp[j]);
right[n - 1] = dp[n - 1];
for (let j = n - 2; j >= 0; j--) right[j] = Math.max(right[j + 1] - 1, dp[j]);
dp = points[r].map((v, j) => v + Math.max(left[j], right[j]));
}
return Math.max(...dp);
}long maxPoints(int[][] points) {
int n = points[0].length;
long[] dp = new long[n];
for (int j = 0; j < n; j++) dp[j] = points[0][j];
for (int r = 1; r < points.length; r++) {
long[] left = new long[n], right = new long[n];
left[0] = dp[0];
for (int j = 1; j < n; j++) left[j] = Math.max(left[j - 1] - 1, dp[j]);
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[r][j] + Math.max(left[j], right[j]);
}
long best = dp[0];
for (int j = 1; j < n; j++) best = Math.max(best, dp[j]);
return best;
}long long maxPoints(vector<vector<int>>& points) {
int n = points[0].size();
vector<long long> dp(points[0].begin(), points[0].end());
for (int r = 1; r < (int)points.size(); r++) {
vector<long long> left(n), right(n);
left[0] = dp[0];
for (int j = 1; j < n; j++) left[j] = max(left[j - 1] - 1, dp[j]);
right[n - 1] = dp[n - 1];
for (int j = n - 2; j >= 0; j--) right[j] = max(right[j + 1] - 1, dp[j]);
for (int j = 0; j < n; j++) dp[j] = points[r][j] + max(left[j], right[j]);
}
return *max_element(dp.begin(), dp.end());
}Explanation
The natural dp is dp[r][j] = best score after picking column j in row r. The transition dp[r][j] = points[r][j] + max over k of (dp[r−1][k] − |j − k|) is correct but costs O(n) per cell, O(n²) per row — too slow for big grids. The trick is to split the absolute value into two directions.
If the previous pick k is at or left of j, the penalty is j − k, so the candidate is dp[k] − (j − k). Define left[j] = the best such candidate for k ≤ j. Walking left to right, left[j] = max(left[j−1] − 1, dp[j]): the running best fades by exactly 1 for every column it travels, which is precisely the distance penalty being paid incrementally.
Symmetrically, right[j] = max(right[j+1] − 1, dp[j]) sweeping right to left covers all k ≥ j. Now the new row is just dp[j] = points[r][j] + max(left[j], right[j]) — every transition for the whole row in two O(n) passes plus one O(n) combine.
Walk the default example [[1,2,3],[1,5,1],[3,1,1]]. Start with dp = [1,2,3]. For row 1 both passes give [1,2,3], so dp = [1+1, 5+2, 1+3] = [2,7,4]. For row 2, left = [2,7,6] and right = [6,7,4]; combining with [3,1,1] yields dp = [9,8,7].
The answer is max(dp) = 9: take 3, shift one column to grab 5, shift one more to grab 3, paying 2 in total. Notice how left[0] = 6 for the last row encoded "the 7 sitting one column away is worth 6 here" without ever scanning all pairs.
Each of the m − 1 row updates does three linear sweeps, so the total time is O(m·n), and we only ever keep the previous row plus two helper arrays, so the extra space is O(n).