Pythonでコインマトリックスが消えることから得られる最大のコインを見つけるためのプログラム

各セル行列[r、c]がそのセルに存在するコインの数を表す2D行列があるとします。 matrix [r、c]からコインを拾うと、行（r --1）と（r + 1）のすべてのコインが消え、2つのセルのmatrix [r、c+1]と行列[r、c-1]。収集できるコインの最大数を見つける必要があります。

したがって、入力が次のような場合

コイン8、6、9、3でセルを選択できるため、出力は26になり、合計は26になります。

これを解決するには、次の手順に従います-

• 関数getmax（）を定義します。これには時間がかかります
• 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の最大値
• return res
• メインの方法から次のようにします-
• 行列が空の場合、
  • 0を返す
• m：=行列の行数
• n：=行列の列数
• row_sum：=サイズmの配列で、0で埋めます
• 0からm-1の範囲のiの場合、do
  • row_sum [i]：=getmax（matrix [i]）
• return 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