สมมติว่าเรามีเมทริกซ์ 2 มิติ โดยที่แต่ละเซลล์เมทริกซ์[r, c] แทนจำนวนเหรียญที่มีอยู่ในเซลล์นั้น เมื่อเราหยิบเหรียญจาก matrix[r, c] เหรียญทั้งหมดที่อยู่ในแถว (r - 1) และ (r + 1) จะหายไป เช่นเดียวกับเหรียญที่ matrix สองเซลล์[r, c + 1] และ เมทริกซ์[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
- สำหรับแต่ละ num ใน arr ทำ
- อุณหภูมิ :=curr_max
- curr_max :=num + prev_max
- prev_max :=สูงสุดของอุณหภูมิและ prev_max
- res :=สูงสุดของ res และ curr_max
- ผลตอบแทน
- จากวิธีหลัก ให้ทำดังนี้ -
- ถ้าเมทริกซ์ว่างเปล่า
- คืน 0
- m :=จำนวนแถวของเมทริกซ์
- n :=จำนวนคอลัมน์ของเมทริกซ์
- row_sum :=อาร์เรย์ขนาด m และเติม 0
- สำหรับฉันในช่วง 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
