1937

class Solution {
    long findMax(long[] dp){
        long ans = dp[0];
        for(int i=1;i<dp.length;i++){
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
    public long maxPoints(int[][] points) {
        long[] leftMax = new long[points[0].length+1];
        long[] rightMax = new long[points[0].length+1];
        long[] dp = new long[points[0].length];
        long ans = 0;
        for(int i=0;i<points.length;i++){
            if(i==0){
                for(int j=0;j<points[0].length;j++){
                    dp[j]=(long)points[0][j];
                }
                ans = findMax(dp);
            }else{
                for(int j=0;j<points[0].length;j++){
                    dp[j] = points[i][j] + Math.max(leftMax[j],rightMax[j]);
                }
            }
            ans = findMax(dp);
            leftMax[0] = dp[0];
            for(int j=1;j<points[0].length;j++){
                leftMax[j] = Math.max(leftMax[j-1]-1,dp[j]);
            }
            rightMax[points[0].length-1]=dp[points[0].length-1];
            for(int j=points[0].length-2;j>=0;j--){
                rightMax[j] = Math.max(dp[j],rightMax[j+1]-1);
            }
        }
        return ans;
    }
}