DSA problem
Maximum Number of Points with Cost
You are given an m x n matrix points of non-negative integers. Starting from any cell in row 0 you collect points moving down one row at a time, picking exactly one cell per row. If you pick column c1 in row r and column c2 in row r + 1, you lose abs(c1 - c2) points as a penalty. Return the maximum total points after picking one cell per row.
A straightforward DP defines dp[r][c] = max points reachable when standing on cell (r, c). The transition is dp[r][c] = points[r][c] + max over c' of (dp[r - 1][c'] - abs(c - c')). Done naively the inner max is O(n) per cell, giving O(m * n^2) time — too slow when both dimensions are 10^5.
The trick is to split the absolute value into two cases. For c' <= c, abs(c - c') = c - c', so the max becomes max(dp[r - 1][c'] + c') - c. For c' >= c, abs(c - c') = c' - c, so the max becomes max(dp[r - 1][c'] - c') + c. Each can be maintained by a single forward sweep (running maxLeft) and a single backward sweep (running maxRight) across row r - 1.
Concretely: precompute leftMax[c] = max(dp[r - 1][c'] - (c - c')) for c' <= c via the recurrence leftMax[c] = max(leftMax[c - 1] - 1, dp[r - 1][c]), and rightMax[c] analogously sweeping right-to-left. Then dp[r][c] = points[r][c] + max(leftMax[c], rightMax[c]). This drops the cost to O(m * n) time and, with rolling rows, O(n) space.
Examples
points = [[1,2,3],[1,5,1],[3,1,1]]9points = [[1,5],[2,3],[4,2]]11points = [[5]]5Constraints
- m == points.length
- n == points[r].length
- 1 <= m, n <= 10^5
- 1 <= m * n <= 10^5
- 0 <= points[r][c] <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.