# 1937. Maximum Number of Points with Cost

• Time: $O(mn)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public: long long maxPoints(vector>& points) { const int n = points[0].size(); // dp[j] := max # points you can have if points[i][j] is the most recent // Cell you picked vector dp(n); for (const vector& row : points) { vector leftToRight(n); long long runningMax = 0; for (int j = 0; j < n; ++j) { runningMax = max(runningMax - 1, dp[j]); leftToRight[j] = runningMax; } vector rightToLeft(n); runningMax = 0; for (int j = n - 1; j >= 0; --j) { runningMax = max(runningMax - 1, dp[j]); rightToLeft[j] = runningMax; } for (int j = 0; j < n; ++j) dp[j] = max(leftToRight[j], rightToLeft[j]) + row[j]; } return *max_element(begin(dp), end(dp)); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public long maxPoints(int[][] points) { final int n = points[0].length; // dp[j] := max # points you can have if points[i][j] is the most recent cell you picked long[] dp = new long[n]; for (int[] row : points) { long[] leftToRight = new long[n]; long runningMax = 0; for (int j = 0; j < n; ++j) { runningMax = Math.max(runningMax - 1, dp[j]); leftToRight[j] = runningMax; } long[] rightToLeft = new long[n]; runningMax = 0; for (int j = n - 1; j >= 0; --j) { runningMax = Math.max(runningMax - 1, dp[j]); rightToLeft[j] = runningMax; } for (int j = 0; j < n; ++j) dp[j] = Math.max(leftToRight[j], rightToLeft[j]) + row[j]; } return Arrays.stream(dp).max().getAsLong(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def maxPoints(self, points: List[List[int]]) -> int: n = len(points[0]) # dp[j] := max # Points you can have if points[i][j] is the most recent cell you picked dp = [0] * n for row in points: leftToRight = [0] * n runningMax = 0 for j in range(n): runningMax = max(runningMax - 1, dp[j]) leftToRight[j] = runningMax rightToLeft = [0] * n runningMax = 0 for j in range(n - 1, - 1, -1): runningMax = max(runningMax - 1, dp[j]) rightToLeft[j] = runningMax for j in range(n): dp[j] = max(leftToRight[j], rightToLeft[j]) + row[j] return max(dp)