在Python中查找从消失的coin矩阵中可以获得的最大硬币数量的程序

假设我们有一个2D矩阵，其中每个单元matrix[r,c]代表该单元格中存在的硬币数量。当我们从matrix[r，c]中取出硬币时，行(r-1)和(r+1)上的所有硬币将消失，并且matrix[r，c + 1]和matrix[r，c-1]处的硬币也会消失。我们必须找到我们可以收集的最大硬币数量。

所以，如果输入是：

那么输出将是26，因为我们可以选择带有硬币8、6、9和3的单元格，总共是26。

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数getmax()，它将获取arr
• prev_max:=0
• curr_max:=0
• res:=0
• 对于arr中的每个数字，执行以下操作：
  • temp:=curr_max
  • curr_max:=num+prev_max
  • prev_max:=temp和prev_max的最大值
  • res:=res和curr_max的最大值
• 返回res
• 从主方法执行以下操作：
  • 如果matrix为空，则
    • 返回0
  • m:=matrix的行数
  • n:=matrix的列数
  • row_sum:=大小为m的数组，并以0填充
  • 对于0到m-1的范围内的i，执行以下操作：
    • row_sum[i]:=getmax(matrix[i])
  • 返回getmax(row_sum)

示例

让我们看一下以下实现，以便更好地理解-

def getmax(arr):
   prev_max, curr_max = 0, 0
   res = 0
   for num in arr:
      temp = curr_max
      curr_max = num + prev_max
      prev_max = max(temp, prev_max)
      res = max(res, curr_max)
   return res

def solve(matrix):
   if not matrix:
      return 0
   m, n = len(matrix), len(matrix[0])
   row_sum = [0 for _ in range(m)]
   for i in range(m):
      row_sum[i] = getmax(matrix[i])
   return getmax(row_sum)

matrix = [
   [2, 8, 7, 6],
   [10, 10, 4, 2],
   [5, 9, 2, 3]
]
print(solve(matrix))

输入

[
[2, 8, 7, 6],
[10, 10, 4, 2],
[5, 9, 2, 3
]

输出

26