3410 - Submatrix Sum Max

Se dă o matrice de numere întregi cu n linii și n coloane.

Cerință

Să se determine suma maximă care se poate obține dintr-o submatrice.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi elementele matricei cu n linii și n coloane.

Date de ieșire

Programul va afișa pe ecran suma maximă care se poate obține dintr-o submatrice.

Restricții de precizări

• 1 ⩽ n ⩽ 300
• Elementele matricei sunt numere întregi din intervalul [-1000, 1000]
• O submatrice poate fi formată dintr-un singur element

Exemplu

Intrare

5

2 4 -1 2 -1

4 -7 1 -6 -1

-9 2 4 5 -7

1 3 -2 6 2

1 -4 -6 -5 8

Ieșire

18

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

def suma_maxima_submatrice(matrice):

   n = len(matrice)  # numărul de linii/coloane din matrice
   # inițializăm matricea de sume prefix cu 0
   prefix_sum = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

   # calculăm matricea de sume prefix
   for i in range(n):
       for j in range(n):
           prefix_sum[i + 1][j + 1] = matrice[i][j] - prefix_sum[i][j] + prefix_sum[i][j + 1] + prefix_sum[i + 1][j]

   max_sum = float('-inf')  # inițializăm suma maximă cu -infinit
   # parcurgem toate submatricile posibile
   for i in range(1, n + 1):
       for j in range(1, n + 1):
           for k in range(i, n + 1):
               for l in range(j, n + 1):
                   # calculăm suma submatricei curente folosind sumele prefix
                   curr_sum = prefix_sum[k][l] - prefix_sum[k][j - 1] - prefix_sum[i - 1][l] + prefix_sum[i - 1][j - 1]
                   max_sum = max(max_sum, curr_sum)  # actualizăm suma maximă dacă este cazul

   return max_sum  # returnăm suma maximă

1. citim datele de intrare

n = int(input()) matrice = [list(map(int, input().split())) for _ in range(n)]

1. afișăm suma maximă a unei submatrici

print(suma_maxima_submatrice(matrice))

</syntaxhighlight>

Explicatie

Submatricea de sumă maximă este

2 4 5

3 -2 6