'''
input dp input[j]+max(LTR[j],RTL[j]) LeftToRight(max(dp[j], do[j-1]-1)) RightToLeft max(dp[j], dp[j+1]-1)
1,2,3 1,2,3 2,7,4 2,7,4
1,5,1 2,7,4 2,7,6 6,7,4
3,1,1 9,8,7
'''
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
rows = len(points)
cols = len(points[0])
dp = [[0] * cols for _ in range(rows)]
for i, value in enumerate(points[0]):
dp[0][i] = value
for i in range(1, rows):
prev_dp = dp[i-1]
left_to_right = dp[i-1][:]
right_to_left = dp[i-1][:]
for j in range(1,cols):
left_to_right[j] = max(left_to_right[j], left_to_right[j-1]-1)
for j in range(cols-2,-1,-1):
right_to_left[j] = max(right_to_left[j], right_to_left[j+1]-1)
for j in range(cols):
dp[i][j] = points[i][j] + max(left_to_right[j], right_to_left[j])
return max(dp[-1])
