3410 - Submatrix Sum Max

From Bitnami MediaWiki

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

Exemplul 1

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
Datele introduse corespund restricțiilor impuse.
18

Exemplul 2

Intrare
313
Ieșire
Datele introduse nu corespund restricțiilor impuse.

Rezolvare

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

def verificare_restrictii(numar, matrix): # functia de verificare a datelor de intrare

   if 1 <= numar <= 300 and all(-1000 <= element <= 1000 for rand in matrix for element in rand):
       return True
   else:
       return False


def suma_maxima_submatrice(numar, matrix):

   # inițializăm matricea de sume prefix cu 0
   prefix_sum = [[0 for _ in range(numar + 1)] for _ in range(numar + 1)]
   # calculăm matricea de sume prefix
   for i in range(numar):
       for j in range(numar):
           prefix_sum[i + 1][j + 1] = matrix[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, numar + 1):
       for j in range(1, numar + 1):
           for k in range(i, numar + 1):
               for lenght in range(j, numar + 1):
                   # calculăm suma submatricei curente folosind sumele prefix
                   curr_sum = prefix_sum[k][lenght] - prefix_sum[k][j - 1] - prefix_sum[i - 1][lenght] + 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ă


if __name__ == '__main__':

   try:
       n = int(input("Introduceti numarul de linii/coloane: "))     # citirea numarului de linii si coloane
       matrice = [list(map(int, input().split())) for _ in range(n)]  # citirea matricei
       if verificare_restrictii(n, matrice):             # verificam datele de intrare
           print("Datele de intrare corespund restrictiilor impuse.")
           print(suma_maxima_submatrice(n, matrice))  # apelam functia de rezolvare
       else:
           print("Datele de intrare nu corespund restrictiilor impuse.")
   # ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
   except ValueError:
       print("Datele de intrare nu corespund restrictiilor impuse.")
   except IndexError:
       print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

Explicație

Submatricea de sumă maximă este:

2 4 5
3 -2 6