पायथन में एक मैट्रिक्स में अधिकतम गैर नकारात्मक उत्पाद खोजने का कार्यक्रम

मान लीजिए कि हमारे पास 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 से n -1 की सीमा में, करो
  - यदि मैं 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]
    - Ans2 :=dp[i-1, j, 1] * मैट्रिक्स[i, j]
    - Ans3 :=dp[i, j-1, 0] * मैट्रिक्स[i, j]
    - Ans4 :=dp[i, j-1, 1] * मैट्रिक्स[i, j]
    - अधिकतम:=अधिकतम उत्तर1, उत्तर2, उत्तर3 और उत्तर4
    - न्यूनतम:=न्यूनतम उत्तर1, उत्तर2, उत्तर3 और उत्तर4
    - यदि अधिकतम <0, तो
      - dp[i, j] :=एक जोड़ी बनाएं (न्यूनतम, न्यूनतम)
    - अन्यथा जब न्यूनतम> 0, तब
      - dp[i, j] :=एक जोड़ी बनाएं (अधिकतम, अधिकतम)
    - अन्यथा,
      - dp[i, j] :=एक जोड़ी बनाएं (अधिकतम, न्यूनतम)
अगर dp[m-1, n-1, 0] <0, तो
- वापसी -1
अन्यथा,
- रिटर्न डीपी[एम-1, एन-1, 0] % पी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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"