Maximum Number of Points with Cost

1public long maxPoints(int[][] points) {
2    int m = points.length, n = points[0].length;
3    long[] dp = new long[n];
4    for (int j = 0; j < n; j++) dp[j] = points[0][j];
5
6    for (int row = 1; row < m; row++) {
7        // Left-to-right scan
8        long[] left = new long[n];
9        left[0] = dp[0];
10        for (int j = 1; j < n; j++) {
11            left[j] = Math.max(left[j-1] - 1, dp[j]);
12        }
13
14        // Right-to-left scan
15        long[] right = new long[n];
16        right[n-1] = dp[n-1];
17        for (int j = n - 2; j >= 0; j--) {
18            right[j] = Math.max(right[j+1] - 1, dp[j]);
19        }
20
21        // Update dp
22        for (int j = 0; j < n; j++) {
23            dp[j] = points[row][j] + Math.max(left[j], right[j]);
24        }
25    }
26
27    long maxVal = 0;
28    for (long val : dp) maxVal = Math.max(maxVal, val);
29    return maxVal;
30}