Skip to content

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<vector<int>>& points) {
    const int n = points[0].size();
    // dp[j] := the maximum number of points you can have if points[i][j] is the
    // most recent cell you picked
    vector<long> dp(n);

    for (const vector<int>& row : points) {
      vector<long> leftToRight(n);
      long runningMax = 0;

      for (int j = 0; j < n; ++j) {
        runningMax = max(runningMax - 1, dp[j]);
        leftToRight[j] = runningMax;
      }

      vector<long> 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[0].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[0])
    # dp[j] := the maximum number of 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)