Editing 2429 - matrice9

== Cerinta ==

Se cere să se găsească o submatrice validă a lui A de arie maximă.

== Date de intrare ==

Fișierul de intrare matrice9.in conține pe prima linie numerele N şi M, separate prin spaţiu. Pe fiecare dintre următoarele N linii se află câte M numere întregi separate prin câte un spaţiu, reprezentând elementele matricei A.

== Date de iesire ==

Fișierul de ieșire matrice9.out va conţine o singură linie pe care vor fi scrise coordonatele l1, c1, l2, c2 (în această ordine şi separate prin câte un spaţiu) ale unei submatrice valide de arie maximă. În cazul în care există mai multe soluţii cu arie maximă, se va afişa oricare dintre ele.

== Restrictii si precizari ==

*1 ≤ N, M ≤ 1000
*70% din teste vor avea N, M ≤ 600
*Elementele matricei A sunt numere întregi din intervalul [-30000, 30000].

== Exemplul 1 ==

; intrare

:2 6

:1 2 5 7 9 10

:3 4 3 5 1 10

; iesire

:Datele introduse corespund restrictiilor impuse. 

:1 1 2 3

== Exemplul 2 ==
; intrare

:3 7

:2 3 6 8 10 11

:4 5 4 6 2 11

; iesire 

:Datele de intrare nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlightlang="python3"line="1">

def este_sir_valid(sir):
    n = len(sir)
    crescator = all(sir[i] < sir[i + 1] for i in range(n - 1))
    descrescator = all(sir[i] > sir[i + 1] for i in range(n - 1))
    return crescator or descrescator

def aria_maxima_submatrice_valida(matrice):
    n = len(matrice)
    m = len(matrice[0])
    max_aria = 0

    for i in range(n):
        for j in range(m):
            sir_linie = [matrice[i][k] for k in range(j, m)]
            submatrice_aria = 0

            for h in range(i, n):
                sir_linie = [matrice[h][k] for k in range(j, m)]
                if este_sir_valid(sir_linie):
                    submatrice_aria += len(sir_linie)
                    max_aria = max(max_aria, submatrice_aria)
                else:
                    break

    return max_aria

# Exemplu de folosire
matrice_A = [
    [1, 2, 3, 7],
    [8, 5, 2, 1],
    [3, 5, 6, 2],
    [4, 1, 5, 6]
]

rezultat = aria_maxima_submatrice_valida(matrice_A)
print("Aria maxima a unei submatrici valide este:", rezultat)

<syntaxhighlight>