Python में मैट्रिक्स में अधिकतम गैर-ऋणात्मक गुणनफल खोजने का प्रोग्राम

मान लीजिए हमारे पास 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 := len(matrix)
n := len(matrix[0])
dp := दिए गए मैट्रिक्स के क्रम का 2D मैट्रिक्स और 0 से भरा
i को 0 से m-1 तक:
- j को 0 से n-1 तक:
  - यदि i == 0 and j == 0:
    - dp[i][j] := [matrix[i][j], matrix[i][j]]
  - अन्यथा यदि i == 0:
    - ans1 := dp[i][j-1][0] * matrix[i][j]
    - dp[i][j] := [ans1, ans1]
  - अन्यथा यदि j == 0:
    - ans1 := dp[i-1][j][0] * matrix[i][j]
    - dp[i][j] := [ans1, ans1]
  - अन्यथा:
    - 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)
    - यदि maximum < 0:
      - dp[i][j] := [minimum, minimum]
    - अन्यथा यदि minimum > 0:
      - dp[i][j] := [maximum, maximum]
    - अन्यथा:
      - dp[i][j] := [maximum, minimum]
यदि dp[m-1][n-1][0] < 0:
- -1 वापस करें
अन्यथा:
- int(dp[m-1][n-1][0] % p) वापस करें

उदाहरण

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

def solve(matrix):
    p = 10**9+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))

इनपुट

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