โปรแกรมค้นหาผลิตภัณฑ์ที่ไม่ใช่ค่าลบสูงสุดในเมทริกซ์ใน 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 :=จำนวนแถวของเมทริกซ์
n :=จำนวนคอลัมน์ของเมทริกซ์
dp :=เมทริกซ์ 2 มิติที่เรียงลำดับตามเมทริกซ์ที่กำหนดและเติมด้วย 0
สำหรับฉันในช่วง 0 ถึง m - 1 ทำ
- สำหรับ j ในช่วง 0 ถึง n - 1 ทำ
  - ถ้าฉันเหมือนกับ 0 และ j เหมือนกับ 0 แล้ว
    - dp[i, j] :=สร้างคู่ (เมทริกซ์[i, j], เมทริกซ์[i, j])
  - มิฉะนั้น เมื่อฉันเหมือนกับ 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]
    - สูงสุด :=สูงสุดของ 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"