Python程序：从消失的硬币矩阵中获取最大硬币数

假设我们有一个二维矩阵，其中每个单元格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中的每个num，执行以下操作：
  • temp := curr_max
  • curr_max := num + prev_max
  • prev_max := temp和prev_max中的最大值
  • res := res和curr_max中的最大值
• 返回res
• 从主方法执行以下操作：
• 如果矩阵为空，则
  • 返回0
• m := 矩阵的行数
• n := 矩阵的列数
• 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

Arnab Chakraborty

更新于：2021年10月16日

146 次浏览

启动您的职业生涯

完成课程获得认证

开始