Editing 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 &les; n &les; 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ă

# citim datele de intrare
n = int(input())
matrice = [list(map(int, input().split())) for _ in range(n)]
# afișăm suma maximă a unei submatrici
print(suma_maxima_submatrice(matrice))


</syntaxhighlight>

==Explicație==

Submatricea de sumă maximă este:
:'''2 4 5'''
:'''3 -2 6'''