LeetCode 1937: Maximum Number of Points with Cost Solution

Master LeetCode problem 1937 (Maximum Number of Points with Cost), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1937. Maximum Number of Points with Cost

Medium

Array Dynamic Programming Matrix

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will iterate over each row while keeping track of the maximum score we can achieve for each cell in that row. At each cell, we update the maximum score based on the scores of the previous row and the distance between the cells.

We will maintain a 2D array dp, where dp[i][j] represents the maximum score we can achieve by selecting cell j in row i. We update dp for each cell based on the maximum score from the previous row and the distance between the cells.

After filling the dp array, the maximum score we can achieve is the maximum value in the last row of dp.

Algorithm:

Initialize a 2D array dp of size m x n, where m is the number of rows and n is the number of columns.
Initialize the first row of dp as the same as the points array.
Iterate over rows starting from the second row:
- For each cell in the current row, update its value using the formula dp[i][j] = points[i][j] + max(dp[i-1][k] - abs(j - k)) for all k in the previous row.
The answer is the maximum value in the last row of dp.

Time Complexity

The time complexity of this solution is O(m * n), where m is the number of rows and n is the number of columns in the points matrix.

Space Complexity

The space complexity of this solution is O(m * n) for the dp array.

Solution Code

class Solution {
    public long maxPoints(int[][] points) {
        int m = points.length;
        int n = points[0].length;
        
        long[][] dp = new long[m][n];
        for (int j = 0; j < n; j++) {
            dp[0][j] = points[0][j];
        }
        
        for (int i = 1; i < m; i++) {
            long[] leftPrefix = new long[n];
            long[] rightPrefix = new long[n];
            
            leftPrefix[0] = dp[i-1][0];
            for (int j = 1; j < n; j++) {
                leftPrefix[j] = Math.max(leftPrefix[j-1], dp[i-1][j] + j);
            }
            
            rightPrefix[n-1] = dp[i-1][n-1] - (n-1);
            for (int j = n-2; j >= 0; j--) {
                rightPrefix[j] = Math.max(rightPrefix[j+1], dp[i-1][j] - j);
            }
            
            for (int j = 0; j < n; j++) {
                dp[i][j] = points[i][j] + Math.max(leftPrefix[j] - j, rightPrefix[j] + j);
            }
        }
        
        long maxPoints = dp[m-1][0];
        for (int j = 1; j < n; j++) {
            maxPoints = Math.max(maxPoints, dp[m-1][j]);
        }
        
        return maxPoints;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1937 (Maximum Number of Points with Cost)?

This page provides optimized solutions for LeetCode problem 1937 (Maximum Number of Points with Cost) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1937 (Maximum Number of Points with Cost)?

The time complexity for LeetCode 1937 (Maximum Number of Points with Cost) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1937 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1937 in Java, C++, or Python.

Back to LeetCode Solutions