পাইথনে একটি ম্যাট্রিক্সে সর্বাধিক অ নেতিবাচক পণ্য খুঁজে বের করার প্রোগ্রাম

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

সুতরাং, যদি ইনপুট মত হয়

2	-4	2
2	-4	2
4	-8	2

তাহলে আউটপুট হবে 256 কারণ পথটি রঙিন,

2	-4	2
2	-4	2
4	-8	2

সুতরাং পণ্য হল [2 * 2 * (-4) * (-8) * 2] =256।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

p :=10^9+7
m :=ম্যাট্রিক্সের সারি গণনা
n :=ম্যাট্রিক্সের কলাম সংখ্যা
dp :=একটি 2d ম্যাট্রিক্স যার ক্রম প্রদত্ত ম্যাট্রিক্সের সাথে এবং 0 দিয়ে পূরণ করুন
আমি 0 থেকে m - 1 রেঞ্জের জন্য, কর
- করুন
  - যদি i 0 এর মত হয় এবং j 0 এর মত হয়, তাহলে
    - dp[i, j] :=একটি জোড়া তৈরি করুন (ম্যাট্রিক্স[i, j], ম্যাট্রিক্স[i, j])
  - অন্যথায় যখন আমি 0 এর সমান, তখন
    - ans1 :=dp[i, j-1, 0] * ম্যাট্রিক্স[i, j]
    - dp[i, j] :=একটি জোড়া তৈরি করুন (ans1, ans1)
  - অন্যথায় যখন j 0 এর মত হয়, তখন
    - ans1 :=dp[i-1, j, 0] * ম্যাট্রিক্স[i, j]
    - dp[i, j] :=একটি জোড়া তৈরি করুন (ans1, ans1)
  - অন্যথায়,
    - ans1 :=dp[i-1, j, 0] * ম্যাট্রিক্স[i, j]
    - আনস2 :=dp[i-1, j, 1] * ম্যাট্রিক্স[i, j]
    - ans3 :=dp[i, j-1, 0] * ম্যাট্রিক্স[i, j]
    - ans4 :=dp[i, j-1, 1] * ম্যাট্রিক্স[i, j]
    - সর্বোচ্চ :=ans1, ans2, ans3 এবং ans4
    - সর্বনিম্ন :=ন্যূনতম ans1, ans2, ans3 এবং ans4
    - যদি সর্বোচ্চ <0 হয়, তাহলে
      - dp[i, j] :=একটি জোড়া তৈরি করুন (সর্বনিম্ন, সর্বনিম্ন)
    - অন্যথায় যখন সর্বনিম্ন> 0, তারপর
      - dp[i, j] :=একটি জোড়া তৈরি করুন (সর্বোচ্চ, সর্বোচ্চ)
    - অন্যথায়,
      - dp[i, j] :=একটি জোড়া তৈরি করুন (সর্বোচ্চ, সর্বনিম্ন)
যদি dp[m-1, n-1, 0] <0, তারপর
- রিটার্ন -1
অন্যথায়,
- রিটার্ন dp[m-1, n-1, 0] % p

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(matrix):
   p = 1e9+7
   m = len(matrix)
   n = len(matrix[0])

   dp = [[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))

ইনপুট

"pqpqrrr"