পাইথনে ডিসঅপিয়ারিং কয়েন্স ম্যাট্রিক্স থেকে সর্বোচ্চ কয়েন সংগ্রহ

একটি ২ডি ম্যাট্রিক্সে প্রতিটি সেলে কয়েন থাকে। সেল (r,c) থেকে কয়েন নিলে সারি r-1 এবং r+1-এর সব কয়েন এবং একই সারির c-1, c+1 সেলের কয়েন মুছে যায়। সর্বোচ্চ কয়েন সংগ্রহ করুন।

ইনপুট উদাহরণ

matrix = [
    [2, 8, 7, 6],
    [10, 10, 4, 2],
    [5, 9, 2, 3]
]

আউটপুট: 26 (সেল ৮, ৬, ৯, ৩ বেছে নিলে)

অ্যালগরিদম

1. প্রতিটি সারির জন্য House Robber সমস্যা সমাধান করুন (এডজেসেন্ট সেল নেওয়া যাবে না)।
2. সারিগুলোর সর্বোচ্চ ভ্যালু নিয়ে আবার House Robber সমাধান করুন (এডজেসেন্ট সারি নেওয়া যাবে না)।

পাইথন কোড

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] * 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))  # 26

ব্যাখ্যা

দুই লেয়ারের DP: প্রথমে প্রতিটি সারি আলাদা করে সমাধান, তারপর সারিগুলোর রেজাল্ট দিয়ে আবার সমাধান। সময় জটিলতা: O(m*n)।