โปรแกรมหาเหรียญสูงสุดจากเมทริกซ์เหรียญหายไปใน Python

สมมติว่าเรามีเมทริกซ์ 2 มิติ ที่แต่ละเซลล์ matrix[r, c] แสดงจำนวนเหรียญในเซลล์นั้น เมื่อเราหยิบเหรียญจาก matrix[r, c] เหรียญทั้งหมดในแถว (r-1) และ (r+1) จะหายไป รวมถึงเหรียญที่เซลล์ matrix[r, c+1] และ matrix[r, c-1] เราต้องหาจำนวนเหรียญสูงสุดที่เก็บได้

เช่น ถ้าอินพุตคือ:

ผลลัพธ์จะเป็น 26 เพราะเราสามารถเลือกเซลล์ที่มีเหรียญ 8, 6, 9 และ 3 รวมเป็น 26

ขั้นตอนการแก้ปัญหา

1. กำหนดฟังก์ชัน getmax(arr):
   • prev_max := 0, curr_max := 0, res := 0
   • สำหรับแต่ละ num ใน arr:
     • temp := curr_max
     • curr_max := num + prev_max
     • prev_max := max(temp, prev_max)
     • res := max(res, curr_max)
   • คืนค่า res
2. จากเมธอดหลัก:
   • ถ้า matrix ว่าง คืนค่า 0
   • m := จำนวนแถว, n := จำนวนคอลัมน์
   • row_sum := อาร์เรย์ขนาด m เติม 0
   • สำหรับ i ในช่วง 0 ถึง m-1: 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