Editing 3410 - Submatrix Sum Max (section)

==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>