在Python中查找从消失的coin矩阵中可以获得的最大硬币数量的程序
假设我们有一个2D矩阵,其中每个单元matrix[r,c]代表该单元格中存在的硬币数量。当我们从matrix[r,c]中取出硬币时,行(r-1)和(r+1)上的所有硬币将消失,并且matrix[r,c + 1]和matrix[r,c-1]处的硬币也会消失。我们必须找到我们可以收集的最大硬币数量。
所以,如果输入是:
2 | 8 | 7 | 6 |
---|---|---|---|
10 | 10 | 4 | 2 |
5 | 9 | 2 | 3 |
那么输出将是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)
- 如果matrix为空,则
示例
让我们看一下以下实现,以便更好地理解-
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