পাইথনে ম্যাট্রিক্সে নন-নেগেটিভ প্রোডাক্ট সর্বোচ্চ করার প্রোগ্রাম

মান লিজিয়ে একটি m x n ম্যাট্রিক্স আছে। আমরা শুরুর কোণা (0,0)-এ আছি, এবং প্রতিটি ধাপে শুধু ডানে বা নিচে যেতে পারি। শুরুর কোণা থেকে বটম-রাইট (m-1,n-1) পর্যন্ত সব পথের মধ্যে নন-নেগেটিভ প্রোডাক্ট সর্বোচ্চ কোনটি সেটি বের করতে হবে। উত্তর বড় হলে 10^9+7 দিয়ে মডুলো রিটার্ন করুন।

যেমন, ইনপুট হলে [[2,-4,2],[2,-4,2],[4,-8,2]], তবে আউটপুট হবে 256 কারণ পথ হল রঙিন সেলগুলো: 2 -> 2 -> -4 -> -8 -> 2, প্রোডাক্ট 2*2*(-4)*(-8)*2 = 256।

সমাধানের ধাপসমূহ

p := 10**9+7
m, n := রো ও কলাম সংখ্যা
dp := ২D ম্যাট্রিক্স, প্রতিটি সেলে [max_prod, min_prod]
প্রতিটি সেল (i,j) এর জন্য:
- যদি (0,0) হয়, তবে dp[0][0] = [val, val]
- যদি প্রথম রো হয়, তবে বামের সেল থেকে প্রোডাক্ট ক্যালকুলেট করুন।
- যদি প্রথম কলাম হয়, তবে উপরের সেল থেকে প্রোডাক্ট ক্যালকুলেট করুন।
- অন্যথায়, উপর ও বামের সেল দুটোর max ও min প্রোডাক্ট থেকে চারটি ক্যাম্বিনেশন বের করুন, তারপর maximum ও minimum নিয়ে dp[i][j] সেট করুন।
যদি dp[m-1][n-1][0] < 0 হয়, তবে -1 রিটার্ন করুন।
অন্যথায় dp[m-1][n-1][0] % p রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(matrix):
    p = 10**9 + 7
    m = len(matrix)
    n = len(matrix[0])
    dp = [[[0,0] for _ in range(n)] for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[i][j] = [matrix[i][j], matrix[i][j]]
            elif i == 0:
                ans1 = dp[i][j-1][0] * matrix[i][j]
                dp[i][j] = [ans1, ans1]
            elif j == 0:
                ans1 = dp[i-1][j][0] * matrix[i][j]
                dp[i][j] = [ans1, ans1]
            else:
                ans1 = dp[i-1][j][0] * matrix[i][j]
                ans2 = dp[i-1][j][1] * matrix[i][j]
                ans3 = dp[i][j-1][0] * matrix[i][j]
                ans4 = dp[i][j-1][1] * matrix[i][j]
                maximum = max(ans1, ans2, ans3, ans4)
                minimum = min(ans1, ans2, ans3, ans4)
                if maximum < 0:
                    dp[i][j] = [minimum, minimum]
                elif minimum > 0:
                    dp[i][j] = [maximum, maximum]
                else:
                    dp[i][j] = [maximum, minimum]
    if dp[m-1][n-1][0] < 0:
        return -1
    else:
        return int(dp[m-1][n-1][0] % p)

matrix = [[2,-4,2],[2,-4,2],[4,-8,2]]
print(solve(matrix))

ইনপুট

[[2,-4,2],[2,-4,2],[4,-8,2]]