# 1937. Maximum Number of Points with Cost

{%hackmd theme-dark %}

To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score.

However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score.

Input: points = [[1,2,3],[1,5,1],[3,1,1]]
Output: 9

- contrains:
- $1 <= m, n <= 10^5$
- $1 <= m * n <= 10^5$
- $0 <= points[r][c] <= 10^5$
-
all pos

1 2 3 r1
1+(1*, 2-1, 3-2) 5+(1-1, 2*, 3-1) 1(1-2, 2-1, 3*) r2
2 7 4 dp r2

1 2 3
l = [1, (1-1, 2), (2-1, 3)]
r = [(1, 2-1) ,(2, 3-1) ,3]

1 3 2 4
l = [1, 1-1 or 3, 3-1 or 2, 2-1 or 4 ]
= [1, 3, 2, 4]
r = [1 or 3-1, 3 or 3-1, 2 or 4-1, 4]
= [2, 3, 3, 4]

nr= [max(l, r)+r[c], ... ]

for r
c op
3 cols

TC O(m*n*n)
TC O(m*n)

123
151
311

[[199]]
big m
big n

check vals

def findMaxCost(grid):# m*n [int] array
    # init
    m = len(grid)
    n = len(grid[0])
    
    #dp loop
    for i in range(1, m):
        # i = 1
        pre = grid[i-1] # 123 -> 274
        # left max
        l = [0]*n  #[0 0 0]
        l[0] = pre[0] #[1 0 0]->[2 0 0]
        for j in range(1, n):
            l[j] = max(l[j-1]-1, pre[j])
        #[1 2 3] -> [2, 7, 6]
        #
        # right max
        r = [0]*n #[0 0 0]
        r[-1] = pre[-1] #[0 0 3] ->[0 0 4]
        for j in range(n-2, -1, -1):
            r[j] = max(r[j+1]-1, pre[j])
        #[1 2 3] -> [6 7 4]
        # decide idx max
        for j in range(n):
            grid[i][j] = max(l[j], r[j]) + grid[i][j]
        #151
        # r1 [1+1, 5+2, 1+3]->[2, 7, 4]
        # r2 [3 1 1] -> [3+(2,6), 1+(7,7), 1+(4, 6)]
    
    # return ans
    #r2 = [9, 8, 7]
    return max(grid[-1]) #9
    
    #TC O(m*n)
    

###### tags: `mock interview` `面試`