1937 - Maximum Number of Points with Cost

 JAVA

• class Solution {
      public long maxPoints(int[][] points) {
          int m = points.length, 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[] prevRowLeft = new long[n];
              System.arraycopy(dp[i - 1], 0, prevRowLeft, 0, n);
              for (int j = n - 2; j >= 0; j--)
                  prevRowLeft[j] -= n - 1 - j;
              long[] prevRowRight = new long[n];
              System.arraycopy(dp[i - 1], 0, prevRowRight, 0, n);
              for (int j = 1; j < n; j++)
                  prevRowRight[j] -= j;
              long[] leftMax = new long[n];
              leftMax[0] = prevRowLeft[0];
              for (int j = 1; j < n; j++)
                  leftMax[j] = Math.max(leftMax[j - 1], prevRowLeft[j]);
              long[] rightMax = new long[n];
              rightMax[n - 1] = prevRowRight[n - 1];
              for (int j = n - 2; j >= 0; j--)
                  rightMax[j] = Math.max(rightMax[j + 1], prevRowRight[j]);
              for (int j = 0; j < n; j++) {
                  long curLeftMax = leftMax[j] + n - 1 - j;
                  long curRightMax = rightMax[j] + j;
                  dp[i][j] = Math.max(curLeftMax, curRightMax) + points[i][j];
              }
          }
          long maxScore = 0;
          for (int j = 0; j < n; j++)
              maxScore = Math.max(maxScore, dp[m - 1][j]);
          return maxScore;
      }
  }

C++

// Time: O(MN)
// Space: O(N)
class Solution {
public:
    long long maxPoints(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size();
        vector<long long> dp(N);
        for (int i = 0; i < N; ++i) dp[i] = A[0][i];
        for (int i = 1; i < M; ++i) {
            vector<long long> next(N);
            long long mx = dp[0];
            for (int j = 0; j < N; ++j) {
                mx = max(mx, dp[j] + j);
                next[j] = A[i][j] - j + mx;
            }
            mx = dp[N - 1] - (N - 1);
            for (int j = N - 1; j >= 0; --j) {
                mx = max(mx, dp[j] - j);
                next[j] = max(next[j], A[i][j] + j + mx);
            }
            swap(next, dp);
        }
        return *max_element(begin(dp), end(dp));
    }
};