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)