Editing 2429 - matrice9 (section)

= Exemplul 1: =
<code>matrice9IN.txt</code>
 2 6
 1 2 5 7 9 10
 3 4 3 5 1 10
<code>matrice9OUT.txt</code>
 1 1 2 3

=== Explicație ===
Aria maximă este <code>6</code>. O altă soluţie de arie maximă ar putea fi <code>1 1 1 6</code> sau <code>1 2 2 4</code> sau <code>1 3 2 5</code> sau <code>1 4 2 6</code>.

== Exemplul 2: ==
<code>matrice9IN.txt</code>
 1001 1001
 1 2 5 7 9 10
 3 4 3 5 1 10
<code>matrice9OUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
N_MAX = 1024
SEQ_UNKNOWN = 0
SEQ_INCREASING = 1
SEQ_DECREASING = 2

N, M = 0, 0
A = [[0] * N_MAX for _ in range(N_MAX)]

Inaltime = [0] * N_MAX
Tip = [SEQ_UNKNOWN] * N_MAX
Inceput = [0] * N_MAX
Contor = 0
Stiva = [0] * N_MAX
Top = [0] * N_MAX

CelMaiBun, CelMaiBun1l, CelMaiBun1c, CelMaiBun2l, CelMaiBun2c = 0, 0, 0, 0, 0

def verifica_restrictiile():
    if not (1 <= N <= 1000 and 1 <= M <= 1000):
        with open("matrice9OUT.txt", "w") as fisier:
            fisier.write("Datele nu corespund restrictiilor impuse\n")
        return False
    return True

def rezolva():
    global N, M, A, Inaltime, Tip, Inceput, Contor, Stiva, Top, CelMaiBun, CelMaiBun1l, CelMaiBun1c, CelMaiBun2l, CelMaiBun2c

    for j in range(M):
        for i in range(N + 1):
            if i == N:
                Inaltime[i] = 0
            elif j == 0:
                Inaltime[i] = 1
            elif Tip[i] == SEQ_UNKNOWN:
                Tip[i] = SEQ_INCREASING if A[i][j] > A[i][j - 1] else SEQ_DECREASING
                Inaltime[i] += 1
            elif Tip[i] == SEQ_INCREASING:
                if A[i][j] < A[i][j - 1]:
                    Inaltime[i] = j - Inceput[i] + 1
                    Inceput[i] = j - 1
                    Tip[i] = SEQ_DECREASING
                else:
                    Inaltime[i] += 1
            elif Tip[i] == SEQ_DECREASING:
                if A[i][j] > A[i][j - 1]:
                    Inaltime[i] = j - Inceput[i] + 1
                    Inceput[i] = j - 1
                    Tip[i] = SEQ_INCREASING
                else:
                    Inaltime[i] += 1

            varf = i
            while Contor > 0 and Inaltime[i] <= Stiva[Contor - 1]:
                varf = Top[Contor - 1]
                if Stiva[Contor - 1] * (i - varf) > CelMaiBun:
                    CelMaiBun = Stiva[Contor - 1] * (i - varf)
                    CelMaiBun1l, CelMaiBun2l = varf, i - 1
                    CelMaiBun1c, CelMaiBun2c = j - Stiva[Contor - 1] + 1, j
                Contor -= 1

            if Inaltime[i] > 0:
                Stiva[Contor] = Inaltime[i]
                Top[Contor] = varf
                Contor += 1

    return CelMaiBun1l + 1, CelMaiBun1c + 1, CelMaiBun2l + 1, CelMaiBun2c + 1

def citeste_rezolva():
    global N, M, A
    with open("matrice9IN.txt", "r") as fisier:
        N, M = map(int, fisier.readline().split())
        if not verifica_restrictiile():
            return
        for i in range(N):
            A[i] = list(map(int, fisier.readline().split()))

    rezultat = rezolva()

    with open("matrice9OUT.txt", "w") as fisier:
        fisier.write(f"{rezultat[0]} {rezultat[1]} {rezultat[2]} {rezultat[3]}\n")

if __name__ == "__main__":
    citeste_rezolva()

</syntaxhighlight>