Python의 행렬에서 음수가 아닌 최대 곱을 찾는 프로그램

m x n 차수의 행렬이 있다고 가정합니다. 처음에는 왼쪽 상단 모서리 셀(0, 0)에 있으며 각 단계에서 행렬에서 오른쪽 또는 아래쪽으로만 이동할 수 있습니다. 이제 왼쪽 위 모서리 셀(0, 0)에서 오른쪽 아래 모서리 셀(m-1, n-1)까지 가능한 모든 경로 중에서 음이 아닌 최대 곱이 있는 경로를 찾아야 합니다. 답이 너무 크면 음수가 아닌 최대 곱 모듈로 10^9+7을 반환합니다.

따라서 입력이 다음과 같으면

경로가 색상이 지정된 경로이므로 출력은 256이 됩니다.

따라서 곱은 [2 * 2 * (-4) * (-8) * 2] =256입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• p :=10^9+7
• m :=행렬의 행 수
• n :=행렬의 열 개수
• dp :=주어진 행렬과 순서가 있고 0으로 채워지는 2차원 행렬
• 0 ~ m - 1 범위의 i에 대해
  • 0 ~ n - 1 범위의 j에 대해 다음을 수행합니다.
    • i가 0과 같고 j가 0과 같으면
      • dp[i, j] :=쌍 만들기 (행렬[i, j], 행렬[i, j])
    • 그렇지 않으면 i가 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]
      • 최대:=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"

출력

256