In the game of Broken Blocks, the player is allowed to move on m x n blocks i.e. m levels and n stone blocks on each level such that one level is vertically above the previous level (as in a staircase), with some of its stone blocks replaced by wooden blocks.
The player at the start of the game is present on the ground level (which should be considered as level 0 or it can be considered as level -1). The player can start from any of the blocks present on the level 0 and start moving further to next levels. The player can only move to the stone-block just above to the present stone-block or diagonally to the left or to the right. The player cant move on the same level.
If the player steps on any of the wooden block (denoted by -1), he will fall off the board and die as the wood-block will not able to hold players weight. Each of the stone-block has some gold coins present on it (wooden blocks doesnt have any coins on them). If at any point the player cant move to further level due to any reason, the game ends and his present total coin score will be considered.
The players aim is to collect as many gold coins as he can without falling off the board.
 
Example 1:
Input: matrix = {{2,5,6},{-1,3,2},{4,-1,5}}
Output: 14
Explanation: Assume 0-based indexing.The matrix 
is:
2 5 6 (level 0)
-1 3 2 (level 1)
4 -1 5 (lever 2)
The player can collect maximum number of coins 
by moving through:matrix[0][2] + matrix[1][1] 
+ matrix[2][2] = 6 + 3 + 5 = 14 coins.
Example 2:
Input: matrix = {{-1,2,3,4},{5,-1,-1,2},
{4,3,-1,-1}}
Output: 11
Explanation: The matrix is:
-1 2 3 4(level 0)
5 -1 -1 2(level 1)
4 3 -1 1(level 2)
The player can collect maximum number of coins 
by moving through:a[0][1] + a[1][0] + a[2][0] 
= 2 + 5 + 4 = 11 coins.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function MaxGold() which takes matrix as input parameter and returns the maximum number of gold coins.
 
Constraints
1<=n,m<=1000
Expected Time Complexity: O(n*m)
Expected Space Complexity: O(1)

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

	def MaxGold(self, matrix):

		# Code here

Solutions:
class Solution:

	def MaxGold(self, matrix):
		l = len(matrix)
		o = len(matrix[0])
		if l == 1:
			r = max(matrix[0])
			if r == -1:
				return 0
			return r
		if o == 1:
			p = matrix[0][0]
			if matrix[0][0] == -1:
				return 0
			for h in range(1, l):
				if matrix[h][0] == -1:
					return p
				matrix[h][0] += matrix[h - 1][0]
				p = matrix[h][0]
			return p
		for h in range(l - 2, -1, -1):
			for g in range(o):
				m = 0
				if matrix[h][g] == -1:
					continue
				if g == 0 and h + 1 < l and (g + 1 < o):
					m = max(m, matrix[h + 1][g], matrix[h + 1][g + 1])
				elif g == o - 1 and h + 1 < l and (g - 1 < o) and (g - 1 >= 0):
					m = max(m, matrix[h + 1][g], matrix[h + 1][g - 1])
				elif h + 1 < l and g + 1 < o and (g > 0) and (g < o - 1):
					m = max(m, matrix[h + 1][g], matrix[h + 1][g + 1], matrix[h + 1][g - 1])
				matrix[h][g] += m
		r = max(matrix[0])
		if r == -1:
			return 0
		return r


class Solution:

	def MaxGold(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		maxi = max(matrix[0])
		if m == 1:
			summa = 0
			for row in matrix:
				if row[0] == -1:
					return summa
				summa += row[0]
			return summa
		for i in range(1, n):
			if set(matrix[i]) == set([-1]):
				return maxi
			if matrix[i][0] == -1:
				matrix[i][0] = float('-inf')
			else:
				matrix[i][0] += max(matrix[i - 1][0], matrix[i - 1][1])
			if matrix[i][-1] == -1:
				matrix[i][-1] = float('-inf')
			else:
				matrix[i][-1] += max(matrix[i - 1][-1], matrix[i - 1][-2])
			for j in range(1, m - 1):
				if matrix[i][j] == -1:
					matrix[i][j] = float('-inf')
				else:
					matrix[i][j] += max(matrix[i - 1][j - 1:j + 2])
			maxi = max(matrix[i] + [maxi])
		return maxi


class Solution:

	def MaxGold(self, mat):
		n = len(mat)
		m = len(mat[0])
		dp = [[0 for i in range(m)] for j in range(n)]
		ma = 0
		for i in range(n):
			for j in range(m):
				if i == 0:
					dp[i][j] = mat[i][j]
				elif mat[i][j] == -1:
					dp[i][j] = -1
				else:
					x = dp[i - 1][j]
					y = -1
					z = -1
					if j - 1 >= 0:
						y = dp[i - 1][j - 1]
					if j + 1 < m:
						z = dp[i - 1][j + 1]
					dp[i][j] = max(x, y, z)
					if dp[i][j] != -1:
						dp[i][j] += mat[i][j]
				ma = max(ma, dp[i][j])
		return ma


class Solution:

	def MaxGold(self, matrix):

		def haha(i, j, arr, n, m, dp):
			if i == n or i < 0 or j == m or (j < 0) or (matrix[i][j] == -1):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			a = arr[i][j] + haha(i + 1, j, arr, n, m, dp)
			b = arr[i][j] + haha(i + 1, j - 1, arr, n, m, dp)
			c = arr[i][j] + haha(i + 1, j + 1, arr, n, m, dp)
			dp[i][j] = max(a, b, c)
			return dp[i][j]
		n = len(matrix)
		m = len(matrix[0])
		dp = [[-1 for _ in range(m)] for _ in range(n)]
		maxi = 0
		for j in range(m):
			maxi = max(maxi, haha(0, j, matrix, n, m, dp))
		return maxi


class Solution:

	def MaxGold(self, mat):
		f = False
		for i in range(len(mat[0])):
			if mat[0][i] > -1:
				f = True
				break
		if f == False:
			return 0
		(r, c, maxx) = (len(mat), len(mat[0]), 0)
		for i in range(0, r):
			for j in range(0, c):
				if i == 0:
					maxx = max(mat[i][j], maxx)
					continue
				if mat[i][j] == -1:
					continue
				x = mat[i - 1][j]
				y = mat[i - 1][j - 1] if j - 1 >= 0 else -1
				z = mat[i - 1][j + 1] if j + 1 < c else -1
				if x == y == z == -1:
					mat[i][j] = -1
					continue
				mat[i][j] += max(x, y, z)
				maxx = max(maxx, mat[i][j])
		return maxx


class Solution:

	def checkValid(self, matrix, row, col):
		if row < 0 or col < 0 or row >= len(matrix) or (col >= len(matrix[0])) or (matrix[row][col] == -1):
			return 0
		else:
			return matrix[row][col]

	def MaxGold(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		res = -1
		if n == 1:
			for i in range(m):
				res = max(res, matrix[0][i])
		for i in range(n - 2, -1, -1):
			for j in range(m):
				if matrix[i][j] == -1:
					continue
				elif j == 0:
					matrix[i][j] = max(matrix[i][j] + self.checkValid(matrix, i + 1, j), matrix[i][j] + self.checkValid(matrix, i + 1, j + 1))
				elif j == m - 1:
					matrix[i][j] = max(matrix[i][j] + self.checkValid(matrix, i + 1, j - 1), matrix[i][j] + self.checkValid(matrix, i + 1, j))
				else:
					matrix[i][j] = max(matrix[i][j] + self.checkValid(matrix, i + 1, j + 1), matrix[i][j] + self.checkValid(matrix, i + 1, j - 1), matrix[i][j] + self.checkValid(matrix, i + 1, j))
		for i in range(m):
			res = max(res, matrix[0][i])
		return res if res != -1 else 0


class Solution:

	def MaxGold(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		dp = [[-1 for _ in range(n)] for _ in range(m)]
		ans = 0
		for i in range(n):
			ans = max(ans, self.check(matrix, m, n, 0, i, dp))
		return ans

	def check(self, matrix, m, n, r, c, dp):
		if r < 0 or r >= m or c < 0 or (c >= n):
			return 0
		if matrix[r][c] == -1:
			return 0
		if dp[r][c] != -1:
			return dp[r][c]
		ans = 0
		ans = max(ans, self.check(matrix, m, n, r + 1, c, dp))
		ans = max(ans, self.check(matrix, m, n, r + 1, c - 1, dp))
		ans = max(ans, self.check(matrix, m, n, r + 1, c + 1, dp))
		ans += matrix[r][c]
		dp[r][c] = ans
		return dp[r][c]


class Solution:

	def MaxGold(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		for i in range(n):
			if matrix[m - 1][i] == -1:
				matrix[m - 1][i] = 0
		for i in range(m - 2, -1, -1):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = 0
					continue
				if n == 1:
					matrix[i][j] += matrix[i + 1][j]
					continue
				elif j == 0:
					matrix[i][j] += max(matrix[i + 1][j + 1], matrix[i + 1][j])
					continue
				elif j == n - 1:
					matrix[i][j] += max(matrix[i + 1][j - 1], matrix[i + 1][j])
					continue
				else:
					matrix[i][j] += max(matrix[i + 1][j - 1], matrix[i + 1][j], matrix[i + 1][j + 1])
					continue
		return max(matrix[0])


class Solution:

	def __init__(self):
		self.mx = 0

	def travel(self, mat, i, j, dp):
		if i < 0 or i >= len(mat) or j < 0 or (j >= len(mat[0])):
			return 0
		if mat[i][j] == -1:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		upval = self.travel(mat, i + 1, j, dp)
		rupval = self.travel(mat, i + 1, j + 1, dp)
		lupval = self.travel(mat, i + 1, j - 1, dp)
		dp[i][j] = max(upval, rupval, lupval) + mat[i][j]
		return dp[i][j]

	def MaxGold(self, matrix):
		dp = [[-1 for i in range(len(matrix[0]))] for j in range(len(matrix))]
		val = 0
		for i in range(len(matrix[0])):
			out = self.travel(matrix, 0, i, dp)
			val = max(val, out)
		return val


class Solution:

	def MaxGold(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		for i in range(n - 2, -1, -1):
			for j in range(0, m):
				if matrix[i][j] != -1:
					bt = matrix[i + 1][j]
					br = matrix[i + 1][j + 1] if j + 1 < m else 0
					bl = matrix[i + 1][j - 1] if j > 0 else 0
					matrix[i][j] += max([bt, br, bl, 0])
		return max([0] + matrix[0])


class Solution:

	def solve(self, matrix, l, p, dp):
		if p >= len(matrix[0]) or p < 0 or l >= len(matrix):
			return 0
		if matrix[l][p] == -1:
			return 0
		if dp[l][p] != -100000000:
			return dp[l][p]
		up = matrix[l][p] + self.solve(matrix, l + 1, p, dp)
		upleft = matrix[l][p] + self.solve(matrix, l + 1, p - 1, dp)
		upright = matrix[l][p] + self.solve(matrix, l + 1, p + 1, dp)
		dp[l][p] = max(up, upleft, upright)
		return dp[l][p]

	def MaxGold(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		dp = [[-100000000 for i in range(m)] for j in range(n)]
		maxi = -1
		for i in range(len(matrix[0])):
			total_coins = self.solve(matrix, 0, i, dp)
			maxi = max(maxi, total_coins)
		return maxi


class Solution:

	def MaxGold(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		memo = {}

		def DFS(i, j):
			if i < 0 or i >= n or j < 0 or (j >= m) or (matrix[i][j] == -1):
				return 0
			elif (i, j) in memo:
				return memo[i, j]
			memo[i, j] = matrix[i][j] + max(DFS(i + 1, j + 1), DFS(i + 1, j - 1), DFS(i + 1, j))
			return memo[i, j]
		ans = 0
		for i in range(m):
			ans = max(ans, DFS(0, i))
		return ans


class Solution:

	def MaxGold(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		dp = [[-float('inf')] * (n + 2) for i in range(m)]
		dp[0] = [0] + matrix[0] + [0]
		ans = max(max(dp[0]), 0)
		for i in range(1, m):
			for j in range(1, n + 1):
				if matrix[i][j - 1] < 0:
					dp[i][j] = -float('inf')
				else:
					dp[i][j] = matrix[i][j - 1] + max(dp[i - 1][j - 1:j + 2])
					if dp[i][j] > ans:
						ans = dp[i][j]
		return ans


class Solution:

	def MaxGold(self, matrix):
		ans = max(0, max(matrix[0]))
		for i in range(1, len(matrix)):
			for j in range(0, len(matrix[0])):
				max_val = -1
				if matrix[i][j] != -1:
					for prev in (j - 1, j, j + 1):
						if prev >= 0 and prev < len(matrix[0]) and (matrix[i - 1][prev] != -1):
							max_val = max(max_val, matrix[i - 1][prev])
					if max_val >= 0:
						matrix[i][j] += max_val
					else:
						matrix[i][j] = -1
					ans = max(ans, matrix[i][j])
				elif matrix[i][j] == -1 and len(matrix[0]) == 1:
					return ans
		return ans


class Solution:

	def MaxGold(self, matrix):
		maxx = max(matrix[0])
		if maxx < 0:
			return 0
		for r in range(1, len(matrix)):
			row_maxx = -1
			for c in range(0, len(matrix[0])):
				if matrix[r][c] == -1:
					continue
				col_maxx = -1
				for (x, y) in [(r - 1, c - 1), (r - 1, c), (r - 1, c + 1)]:
					if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and (matrix[x][y] != -1):
						col_maxx = max(col_maxx, matrix[x][y])
				if col_maxx >= 0:
					matrix[r][c] += col_maxx
					row_maxx = max(row_maxx, matrix[r][c])
				else:
					matrix[r][c] = -1
			if row_maxx > 0:
				maxx = max(maxx, row_maxx)
			else:
				return maxx
		return maxx


class Solution:

	def MaxGold(self, matrix):
		L = len(matrix)
		if not L:
			return 0
		ans = max(0, max(matrix[0]))
		cols = len(matrix[0])
		for row in range(1, L):
			for col in range(cols):
				if matrix[row][col] != -1:
					max_val = -1
					for prev_col in (col - 1, col, col + 1):
						if prev_col >= 0 and prev_col < cols and (matrix[row - 1][prev_col] != -1):
							max_val = max(max_val, matrix[row - 1][prev_col])
					if max_val >= 0:
						matrix[row][col] += max_val
					else:
						matrix[row][col] = -1
					ans = max(ans, matrix[row][col])
				elif matrix[row][col] == -1 and cols == 1:
					return ans
		return ans


class Solution:

	def MaxGold(self, matrix):
		ans = 0

		def fun(i, j, matrix, dp):
			nonlocal ans
			if i == len(matrix):
				return 0
			if j < 0 or j == len(matrix[i]):
				return 0
			if matrix[i][j] == -1:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			(t1, t2, t3) = (fun(i + 1, j, matrix, dp), fun(i + 1, j - 1, matrix, dp), fun(i + 1, j + 1, matrix, dp))
			temp = matrix[i][j] + max([t1, t2, t3])
			ans = max(ans, temp)
			dp[i][j] = temp
			return dp[i][j]
		dp = [[-1 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
		for j in range(len(matrix[0])):
			fun(0, j, matrix, dp)
		return ans


class Solution:

	def MaxGold(self, matrix):
		n = len(matrix[0])
		m = len(matrix)
		ans = 0
		for i in range(m):
			flag = False
			for j in range(n):
				if i == 0:
					flag = True
					ans = max(ans, matrix[i][j])
				if matrix[i][j] == -1:
					continue
				a = matrix[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else -1
				b = matrix[i - 1][j] if i - 1 >= 0 else -1
				c = matrix[i - 1][j + 1] if i - 1 >= 0 and j + 1 < n else -1
				if a == -1 and b == -1 and (c == -1):
					continue
				matrix[i][j] += max(a, max(b, c))
				flag = True
				ans = max(ans, matrix[i][j])
			if flag == False:
				return ans
		return ans


class Solution:

	def isValidPosition(self, matrix, cell):
		(row, col) = cell
		if row >= 0 and row < len(matrix) and (col >= 0) and (col < len(matrix[0])):
			return True
		return False

	def maxGoldFromCell(self, matrix, cell):
		(row, col) = cell
		if self.max_gold[row][col] != -1:
			return self.max_gold[row][col]
		if matrix[row][col] == -1:
			self.max_gold[row][col] = 0
			return 0
		ans = 0
		for dis in [0, 1, -1]:
			if self.isValidPosition(matrix, (row + 1, col + dis)):
				ans = max(ans, self.maxGoldFromCell(matrix, (row + 1, col + dis)))
		self.max_gold[row][col] = ans + matrix[row][col]
		return self.max_gold[row][col]

	def MaxGold(self, matrix):
		if not matrix:
			return 0
		rows = len(matrix)
		cols = len(matrix[0])
		if not cols:
			return 0
		self.max_gold = [[-1] * cols for _ in range(rows)]
		for col in range(cols):
			self.maxGoldFromCell(matrix, (0, col))
		return max(self.max_gold[0])


class Solution:

	def MaxGold(self, mat):
		t = max(mat[0])
		n = len(mat)
		m = len(mat[0])
		for i in range(1, n):
			for j in range(m):
				a = -float('inf')
				if mat[i][j] == -1:
					mat[i][j] = -float('inf')
				a = max(a, mat[i - 1][j] + mat[i][j])
				if j - 1 >= 0:
					a = max(a, mat[i - 1][j - 1] + mat[i][j])
				if j + 1 < m:
					a = max(a, mat[i - 1][j + 1] + mat[i][j])
				mat[i][j] = a
				t = max(t, a)
				t = max(t, 0)
		return t


class Solution:

	def MaxGold(self, matrix):
		col_count = len(matrix[0])
		for (row_num, row) in enumerate(matrix):
			if row_num == 0:
				continue
			for (col_num, value) in enumerate(row):
				prev_row = row_num - 1
				(top_left, top, top_right) = (-1, -1, -1)
				if prev_row >= 0:
					if col_num - 1 >= 0:
						top_left = matrix[prev_row][col_num - 1]
					top = matrix[prev_row][col_num]
					if col_num + 1 < col_count:
						top_right = matrix[prev_row][col_num + 1]
				if value != -1 and max(top_left, top, top_right) != -1:
					matrix[row_num][col_num] = max(top_left, top, top_right) + value
				else:
					matrix[row_num][col_num] = -1
		return max(max(list(map(max, matrix))), 0)


class Solution:

	def MaxGold(self, matrix):
		mymap = {}

		def dfs(i, j):
			if j < 0 or i == len(matrix) or j == len(matrix[0]) or (matrix[i][j] == -1):
				return 0
			if (i, j) in mymap:
				return mymap[i, j]
			x = matrix[i][j]
			z = float('-inf')
			z = max(z, x + dfs(i + 1, j))
			z = max(z, x + dfs(i + 1, j + 1))
			z = max(z, x + dfs(i + 1, j - 1))
			mymap[i, j] = z
			return z
		ans = float('-inf')
		for i in range(len(matrix[0])):
			ans = max(ans, dfs(0, i))
		return ans


class Solution:

	def MaxGold(self, matrix):
		r = len(matrix)
		c = len(matrix[0])
		directions = [[-1, -1], [-1, 0], [-1, 1]]
		max_val = 0
		for i in range(r):
			flag = 0
			for j in range(c):
				if i == 0:
					flag = 1
					max_val = max(max_val, matrix[i][j])
					continue
				if matrix[i][j] == -1:
					continue
				val = matrix[i][j]
				for d in directions:
					cord = [i + d[0], j + d[1]]
					if (cord[0] >= 0 and cord[0] < r) and (cord[1] >= 0 and cord[1] < c) and (matrix[cord[0]][cord[1]] != -1):
						flag = 1
						matrix[i][j] = max(matrix[i][j], val + matrix[cord[0]][cord[1]])
						max_val = max(max_val, matrix[i][j])
			if flag == 0 and i != 0:
				return max_val
		return max_val


class Solution:

	def MaxGold(self, matrix):
		f = False
		for i in range(len(matrix[0])):
			if matrix[0][i] > -1:
				f = True
				break
		if f == False:
			return 0
		(r, c, maxx) = (len(matrix), len(matrix[0]), 0)
		for i in range(r):
			for j in range(c):
				if i == 0:
					maxx = max(matrix[i][j], maxx)
					continue
				if matrix[i][j] == -1:
					continue
				down = matrix[i - 1][j]
				left_diag = matrix[i - 1][j - 1] if j - 1 >= 0 else -1
				right_diag = matrix[i - 1][j + 1] if j + 1 < c else -1
				if down == left_diag == right_diag == -1:
					matrix[i][j] = -1
					continue
				matrix[i][j] += max(down, left_diag, right_diag)
				maxx = max(maxx, matrix[i][j])
		return maxx


class Solution:

	def MaxGold(self, matrix):
		if len(matrix) == 0 or len(matrix[0]) == 0:
			return 0
		scores = self.initScoreMatrix(matrix)
		self.fillScoresMatrixBottomUp(matrix, scores)
		assert len(matrix) > 0
		return max(scores[0])

	def fillScoresMatrixBottomUp(self, matrix, scores):
		assert len(matrix) > 0
		for j in range(len(matrix[-1])):
			if matrix[-1][j] != -1:
				scores[-1][j] = matrix[-1][j]
		for i in range(len(matrix) - 2, -1, -1):
			for j in range(len(matrix[i])):
				if matrix[i][j] == -1:
					continue
				else:
					bottom = scores[i + 1][j]
					diagLeft = 0
					diagRight = 0
					if 0 <= j - 1 < len(matrix[i + 1]):
						diagLeft = scores[i + 1][j - 1]
					if 0 <= j + 1 < len(matrix[i + 1]):
						diagRight = scores[i + 1][j + 1]
					scores[i][j] = matrix[i][j] + max(bottom, diagLeft, diagRight)

	def initScoreMatrix(self, matrix):
		return [[0 for j in range(len(matrix[i]))] for i in range(len(matrix))]


class Solution:

	def MaxGold(self, matrix):
		r = len(matrix)
		c = len(matrix[0])
		max_val = 0
		for i in range(r):
			flag = 0
			for j in range(c):
				if i == 0:
					flag = 1
					max_val = max(max_val, matrix[i][j])
				else:
					if matrix[i][j] == -1:
						continue
					a = matrix[i - 1][j] if i - 1 >= 0 else -1
					b = matrix[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else -1
					c1 = matrix[i - 1][j + 1] if i - 1 >= 0 and j + 1 < c else -1
					if a == -1 and b == -1 and (c1 == -1):
						continue
					matrix[i][j] += max(a, b, c1)
					max_val = max(max_val, matrix[i][j])
					flag = 1
			if flag == 0:
				return max_val
		return max_val


class Solution:

	def MaxGold(self, matrix):
		arr = matrix
		(m, n) = (len(arr), len(arr[0]))
		for i in range(m - 2, -1, -1):
			for j in range(n):
				if arr[i][j] == -1:
					continue
				a = arr[i + 1][j - 1] if j > 0 else 0
				b = arr[i + 1][j]
				c = arr[i + 1][j + 1] if j + 1 < n else 0
				arr[i][j] += max(a, b, c, 0)
		return max(max(arr[0]), 0)


class Solution:

	def MaxGold(self, matrix):
		n = matrix[0]
		for (i, val) in enumerate(n):
			if val == -1:
				n[i] = float('-inf')
		max_val = max(n)
		for (x, line) in enumerate(matrix[1:]):
			new_n = [0] * len(matrix[0])
			for (y, field) in enumerate(line):
				if field < 0:
					new_n[y] = float('-inf')
				else:
					if y > 0:
						val1 = n[y - 1]
					else:
						val1 = float('-inf')
					val2 = n[y]
					if y < len(n) - 1:
						val3 = n[y + 1]
					else:
						val3 = float('-inf')
					if field == 0:
						val4 = 0
					else:
						val4 = float('-inf')
					new_n[y] = max(val1, val2, val3, val4) + field
					max_val = max(new_n[y], max_val)
			n = new_n
		if max_val == float('-inf'):
			return 0
		return max_val


class Solution:

	def MaxGold(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])

		def block(r, c):
			if r < 0 or c < 0 or r >= rows or (c >= cols) or (matrix[r][c] == -1):
				return 0
			if dp[r][c] != -1:
				return dp[r][c]
			count = 0
			down = block(r + 1, c)
			left = block(r + 1, c - 1)
			right = block(r + 1, c + 1)
			count = matrix[r][c] + max(left, down, right)
			dp[r][c] = count
			return count
		dp = [[-1 for i in range(cols)] for j in range(rows)]
		gold = float('-inf')
		for i in range(cols):
			gold = max(gold, block(0, i))
		return gold


class Solution:

	def MaxGold(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		ans = 0
		for i in range(rows):
			for j in range(cols):
				if i == 0:
					ans = max(ans, matrix[i][j])
				elif matrix[i][j] != -1:
					x = y = z = -1
					y = matrix[i - 1][j]
					if j != 0:
						x = matrix[i - 1][j - 1]
					if j != cols - 1:
						z = matrix[i - 1][j + 1]
					res = max(x, y, z)
					if res == -1:
						matrix[i][j] = -1
					else:
						matrix[i][j] += res
					ans = max(ans, matrix[i][j])
		return ans


class Solution:

	def MaxGold(self, matrix):

		def helper(r, c):
			if r < 0 or c < 0 or r >= len(matrix) or (c >= len(matrix[0])) or (matrix[r][c] == -1):
				return 0
			if dp[r][c] != -1:
				return dp[r][c]
			count = 0
			down = helper(r + 1, c)
			right = helper(r + 1, c + 1)
			left = helper(r + 1, c - 1)
			count = matrix[r][c] + max(left, down, right)
			dp[r][c] = count
			return count
		dp = [[-1 for i in range(len(matrix[0]))] for j in range(len(matrix))]
		ans = float('-inf')
		for i in range(len(matrix[0])):
			ans = max(ans, helper(0, i))
		return ans


class Solution:

	def MaxGold(self, matrix):

		def helper(i, j):
			if i < 0 or j < 0 or i >= len(matrix) or (j >= len(matrix[0])) or (matrix[i][j] == -1):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			d = helper(i + 1, j)
			r = helper(i + 1, j + 1)
			l = helper(i + 1, j - 1)
			count = matrix[i][j] + max(d, r, l)
			dp[i][j] = count
			return count
		ans = float('-inf')
		dp = [[-1 for i in range(len(matrix[0]))] for j in range(len(matrix))]
		for i in range(len(matrix[0])):
			ans = max(ans, helper(0, i))
		return ans


class Solution:

	def MaxGold(self, matrix):
		for i in range(len(matrix) - 2, -1, -1):
			for j in range(len(matrix[0])):
				if matrix[i][j] != -1:
					left_diag = 0
					right_diag = 0
					front = matrix[i + 1][j]
					if j > 0:
						left_diag = matrix[i + 1][j - 1]
					if j < len(matrix[0]) - 1:
						right_diag = matrix[i + 1][j + 1]
					matrix[i][j] += max(left_diag, right_diag, front, 0)
		max_gold = max(matrix[0])
		return max(max_gold, 0)


class Solution:

	def MaxGold(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		for i in range(rows - 2, -1, -1):
			for j in range(cols):
				if matrix[i][j] != -1:
					if i + 1 >= 0 and i + 1 < rows:
						if j + 1 >= 0 and j + 1 < cols and (j - 1 >= 0) and (j - 1 < cols):
							diag_right = matrix[i + 1][j + 1] if matrix[i + 1][j + 1] != -1 else 0
							diag_left = matrix[i + 1][j - 1] if matrix[i + 1][j - 1] != -1 else 0
							below = matrix[i + 1][j] if matrix[i + 1][j] != -1 else 0
							matrix[i][j] += max(below, diag_right, diag_left)
						elif j + 1 >= 0 and j + 1 < cols:
							diag_right = matrix[i + 1][j + 1] if matrix[i + 1][j + 1] != -1 else 0
							below = matrix[i + 1][j] if matrix[i + 1][j] != -1 else 0
							matrix[i][j] += max(below, diag_right)
						elif j - 1 >= 0 and j - 1 < cols:
							diag_left = matrix[i + 1][j - 1] if matrix[i + 1][j - 1] != -1 else 0
							below = matrix[i + 1][j] if matrix[i + 1][j] != -1 else 0
							matrix[i][j] += max(below, diag_left)
						else:
							below = matrix[i + 1][j] if matrix[i + 1][j] != -1 else 0
							matrix[i][j] += below
		temp = max(matrix[0])
		return temp if temp != -1 else 0


class Solution:

	def MaxGold(self, matrix):
		if max(matrix[0]) == -1:
			return 0
		(m, n) = (len(matrix), len(matrix[0]))
		ans = max(0, max(matrix[0]))
		for i in range(m - 2, -1, -1):
			for j in range(0, n):
				if matrix[i][j] != -1:
					p = 0
					p = max(p, matrix[i + 1][j])
					if j - 1 >= 0:
						p = max(p, matrix[i + 1][j - 1])
					if j + 1 < n:
						p = max(p, matrix[i + 1][j + 1])
					matrix[i][j] += p
		return max(matrix[0])


class Solution:

	def solve(self, i, j):
		if i == self.n - 1:
			return self.mat[i][j]
		if self.dp[i][j] != None:
			return self.dp[i][j]
		for r in [-1, 0, 1]:
			if j + r >= 0 and j + r < self.m and (self.mat[i + 1][j + r] != -1):
				x = self.solve(i + 1, j + r)
				if x == None:
					continue
				if self.dp[i][j] == None:
					self.dp[i][j] = self.mat[i][j] + x
				else:
					self.dp[i][j] = max(self.dp[i][j], self.mat[i][j] + x)
		if self.dp[i][j] == None:
			return max(0, self.mat[i][j])
		return self.dp[i][j]

	def MaxGold(self, mat):
		self.mat = mat
		self.n = len(mat)
		self.m = len(mat[0])
		self.dp = [[None for j in range(self.m)] for i in range(self.n)]
		a = [self.solve(0, j) for j in range(self.m)]
		ans = 0
		for i in a:
			if i != None:
				ans = max(ans, i)
		return ans


class Solution:

	def MaxGold(self, matrix):
		self.dict = {}
		m = len(matrix)
		n = len(matrix[0])

		def getVal(matrix, x, y):
			if x < 0 or x >= m or y < 0 or (y >= n):
				return 0
			return matrix[x][y]

		def dfs(matrix, x, y):
			if x < 0:
				return
			elif matrix[x][y] == -1:
				matrix[x][y] = 0
			else:
				matrix[x][y] = matrix[x][y] + max(getVal(matrix, x + 1, y), getVal(matrix, x + 1, y - 1), getVal(matrix, x + 1, y + 1))
		for i in range(m - 1, -1, -1):
			for j in range(n):
				dfs(matrix, i, j)
		return max(matrix[0])


from functools import lru_cache

class Solution:

	def MaxGold1(self, matrix, row, col, lookup):
		if row < 0 or row > len(matrix) - 1 or col < 0 or (col > len(matrix[0]) - 1):
			return 0
		if matrix[row][col] == -1:
			return 0
		if lookup[row][col] != -1:
			return lookup[row][col]
		goldCoins = 0
		goldCoins = max(goldCoins, self.MaxGold1(matrix, row + 1, col, lookup))
		goldCoins = max(goldCoins, self.MaxGold1(matrix, row + 1, col - 1, lookup))
		goldCoins = max(goldCoins, self.MaxGold1(matrix, row + 1, col + 1, lookup))
		goldCoins += matrix[row][col]
		lookup[row][col] = goldCoins
		return goldCoins

	def MaxGold(self, matrix):
		lookup = [[-1 for i in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)]
		goldCoins = 0
		for i in range(len(matrix[0])):
			goldCoins = max(goldCoins, self.MaxGold1(matrix, 0, i, lookup))
		return goldCoins


class Solution:

	def MaxGold(self, matrix):
		(Row, Col) = (len(matrix), len(matrix[0]))

		def dfs(r, c, dp):
			if r < 0 or c < 0 or r >= Row or (c >= Col) or (matrix[r][c] == -1):
				return 0
			if dp[r][c] != -1:
				return dp[r][c]
			a = matrix[r][c] + dfs(r + 1, c, dp)
			b = matrix[r][c] + dfs(r + 1, c + 1, dp)
			x = matrix[r][c] + dfs(r + 1, c - 1, dp)
			dp[r][c] = max(a, b, x)
			return dp[r][c]
		res = 0
		dp = [[-1 for _ in range(Col)] for _ in range(Row)]
		for i in range(Col):
			res = max(dfs(0, i, dp), res)
		return res


class Solution:

	def MaxGold(self, mat):
		(tr, tc) = (len(mat), len(mat[0]))
		for r in range(tr - 2, -1, -1):
			for c in range(tc):
				if mat[r][c] != -1:
					a = mat[r + 1][c - 1] if c > 0 else -1
					b = mat[r + 1][c]
					c1 = mat[r + 1][c + 1] if c < tc - 1 else -1
					add = max(a, b, c1)
					if add != -1:
						mat[r][c] += add
		ans = max(mat[0])
		return ans if ans != -1 else 0