Python程式：從消失的硬幣矩陣中獲取最大硬幣數

假設我們有一個二維矩陣，其中每個單元格matrix[r, c]表示該單元格中存在的硬幣數量。當我們從matrix[r, c]拾取硬幣時，第(r - 1)行和(r + 1)行上的所有硬幣都將消失，以及matrix[r, c + 1]和matrix[r, c - 1]這兩個單元格中的硬幣。我們必須找到我們可以收集到的最大硬幣數量。

因此，如果輸入如下所示：

2876
101042
5923

那麼輸出將是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

更新於：2021年10月16日

146 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始
廣告