1937. Maximum Number of Points with Cost

Problem Statement

1937. Maximum Number of Points with Cost

Medium

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, c₁) and (r + 1, c₂) will subtract abs(c₁ - c₂) 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:

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:

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

Java

Source file

class Solution {
    public long maxPoints(int[][] points) {
        int cols = points[0].length;
        long[] prevRow = new long[cols], currRow = new long[cols];
        for(int[] row: points){
            long runningMax = 0;
            for(int j=0; j<cols; j++)
                currRow[j] = runningMax = Math.max(runningMax-1, prevRow[j]);    // runningMax had best outcome until `j-1`th column 
                // since `j` col element can only be 1 less than runningMax due 1 extra penalty from all left prevRow elems
                // so either `runningMax-1` or if directly above elem is selected then `prevRow[j]` 
                // (which was not considered in runningMax bcz it does not fall within j-1 elems on prevRow) 
            runningMax = 0; // same as above but for elems on the right
            for(int j=cols-1; j>=0; j--)
                currRow[j] = Math.max(runningMax = Math.max(runningMax-1, prevRow[j]), currRow[j])+row[j];
            prevRow = currRow;
        }
        long ans = 0;
        for(int j=0; j<cols; j++)
            ans = Math.max(ans, prevRow[j]);
        return ans;
    }
}