LeetCode 1937. Maximum Number of Points with Cost

[Woodyiiiiiii]

class Solution {
    public long maxPoints(int[][] points) {
        
        int m = points.length, n = points[0].length;
        long ans = 0;
        long[] dp = new long[n];
        
        // 每次已经算上该位点的point
        for (int j = 0; j < n; ++j) {
            dp[j] = points[0][j];
        }
        // 之所以从左到右从右到左，是为了算出“区域”最大分数，此后计算完后dp数组
        // 每个值可能不包含每个位点的point了，只代表包括该位点的区域的最大值
        // 这样做是为了下一行的计算做准备
        for (int j = 1; j < n; ++j) {
            dp[j] = Math.max(dp[j - 1] - 1, dp[j]);    
        }
        for (int j = n - 2; j >= 0; --j) {
            dp[j] = Math.max(dp[j], dp[j + 1] - 1);
        }
        
        for (int i = 1; i < m; ++i) {
            
            for (int j = 0; j < n; ++j) {
                dp[j] += points[i][j];
            }
            
            for (int j = 1; j < n; ++j) {
                dp[j] = Math.max(dp[j - 1] - 1, dp[j]);    
            }
            for (int j = n - 2; j >= 0; --j) {
                dp[j] = Math.max(dp[j], dp[j + 1] - 1);
            }
            
        }

        for (int j = 0; j < n; ++j) {
            ans = Math.max(ans, dp[j]);
        }
        return ans;
        
    }
}