# 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.size(); // dp[j] := the maximum number of 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 ranges::max(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 31 class Solution { public long maxPoints(int[][] points) { final int n = points.length; // dp[j] := the maximum number of 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 24 class Solution: def maxPoints(self, points: List[List[int]]) -> int: n = len(points) # dp[j] := the maximum number of points you can have if points[i][j] is the # most recent cell you picked dp =  * n for row in points: leftToRight =  * n runningMax = 0 for j in range(n): runningMax = max(runningMax - 1, dp[j]) leftToRight[j] = runningMax rightToLeft =  * 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)