1937. Maximum Number of Points with Cost

Latest:

https://www.youtube.com/watch?v=ik1y7fz8AOc

class Solution {
    public long maxPoints(int[][] points) {
        int m = points.length;
        int n = points[0].length;
        long[] prevRow = new long[n];
        long[] curRow = new long[n];
        
        for (int j = 0; j < n; j++) { // for big number add...use long
            prevRow[j] = points[0][j];
        }
        long result = 0;

        for (int i = 1; i < m; i++) {
            long[] leftMax = new long[n];
            long[] rightMax = new long[n];

            leftMax[0] = prevRow[0];
            for (int j = 1; j < n; j++) {
                leftMax[j] = Math.max(leftMax[j-1] - 1, prevRow[j]);
            }

            rightMax[n-1] = prevRow[n-1];
            for (int j = n-2; j >= 0; j--) {
                rightMax[j] = Math.max(rightMax[j+1] - 1, prevRow[j]);
            }
            for (int j = 0; j < n; j++) {
                curRow[j] = points[i][j];
                curRow[j] += Math.max(leftMax[j], rightMax[j]);
            }
            prevRow = curRow;
        }

        for (int j = 0; j < n; j++) {
            result = Math.max(result, prevRow[j]); // for only one row case, if it's one row, then ans is in prevRow
        }
        return result;
    }
}
/**

cal left max array
   right max  
if m = 3, left start from 1 , right start from m-2
 left max = left[1] = max(left[1-1] - 1, prev_row[1])  
 right max = right[1] = max(right[3-2] - 1, prev_row[1]) 
so we can have left max and right max
curr_row[1] = curr_row[1] + max(left_max[1], right_max[1])
continuously cal to last row, then ans is the max(last_row)

          1 2 3
left max for 5          ->.  5 + max(1a - 1, 2) = 7
          1a 5 1c
right max for 5.        ->  5 + max(1c -1, 2) =  7

      1. 2 3
left. 1. 2 3
right 1  2 3
      1  5.1 ->  1 + max(1, 1), 5 + max(2, 2), 1 + max(3, 3) = 
      2  7 4 

so 1 5 1 to
          2 7 4
left      2 7 6          
right     6 7 4 
          3 1 1.   3 + max(left[0], right[0]) = 3 + max(2, 6) = 9

          9 8 7.  ->.  max(last row) = 9

so this way is 
T: O(mn), m is row, n is col, for each row, cal left_max (n), and right_max(n) -> m*(2n)
S: O(n), left_max, right_max array          
 */

like 931, 但分支太多, 所以 dfs + memo 會不過 (931 只有 3個分支, 這題有 n 個分支（n is num of col)

DFS + memo (Time Limit Exceeded

T: O(col^row)

S: O(row*col)

DP

another explain

Previous1289. Minimum Falling Path Sum IINext562. Longest Line of Consecutive One in Matrix (3D DP)

Last updated

Was this helpful?