पायथन में गायब होने वाले सिक्कों के मैट्रिक्स से अधिकतम सिक्के प्राप्त करने का प्रोग्राम

मान लीजिए हमारे पास एक 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 में प्रत्येक num के लिए, करें:
  - temp := curr_max
  - curr_max := num + prev_max
  - prev_max := max(temp, prev_max)
  - res := max(res, curr_max)
- res लौटाएं
मुख्य विधि से निम्नलिखित करें:
- यदि matrix खाली है, तो:
  - 0 लौटाएं
- m := matrix की पंक्ति संख्या
- n := matrix की स्तंभ संख्या
- 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]]