โปรแกรมหาผลคูณไม่ติดลบสูงสุดในเมทริกซ์ใน Python

ปัญหา

เมทริกซ์ m x n เริ่ม (0,0) ไป (m-1,n-1) เดินขวาหรือลงอย่างเดียว หาเส้นทางที่ผลคูณไม่ติดลบสูงสุด modulo 1e9+7

ตัวอย่าง

[[2,-4,2],[2,-4,2],[4,-8,2]] → 256 (เส้นทาง 2→2→-4→-8→2 ผลคูณ 256)

ขั้นตอนการแก้ปัญหา

1. p := 10^9+7, m, n := rows, cols
2. dp[i][j] := [max_product, min_product] ถึง (i,j)
3. DP:
   • ฐาน: dp[0][0] = [val, val]
   • ขอบบน: dp[0][j] = [dp[0][j-1][0]*val, dp[0][j-1][0]*val]
   • ขอบซ้าย: dp[i][0] = [dp[i-1][0][0]*val, dp[i-1][0][0]*val]
   • กลาง: คำนวณ 4 ค่าจากบนและซ้าย หา max/min:
     • ถ้า max < 0: dp = [min, min]
     • ถ้า min > 0: dp = [max, max]
     • มิฉะนั้น: dp = [max, min]
4. ถ้า dp[m-1][n-1][0] < 0: คืน -1 มิฉะนั้น คืน dp[m-1][n-1][0] % p

การนำไปใช้งาน (Python)

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):
            val = matrix[i][j]
            if i == 0 and j == 0:
                dp[i][j] = [val, val]
            elif i == 0:
                ans1 = dp[i][j-1][0] * val
                dp[i][j] = [ans1, ans1]
            elif j == 0:
                ans1 = dp[i-1][j][0] * val
                dp[i][j] = [ans1, ans1]
            else:
                ans1 = dp[i-1][j][0] * val
                ans2 = dp[i-1][j][1] * val
                ans3 = dp[i][j-1][0] * val
                ans4 = dp[i][j-1][1] * val
                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 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]]

เอาต์พุต

256