Editing 2629 - H3

== Enunt ==

Tocmai ai primit cadou de ziua ta un șir de numere naturale '''a[1], a[2], …, a[n]'''. Ca să te simți împlinit, trebuie să determini lungimea maximă a unei secvențe cu proprietatea că oricare două valori din secvență sunt distincte.

== Cerinta ==

Determină lungimea maximă cerută și anul viitor vei mai primi un șir!

== Date de intrare ==

Programul citește de la tastatură numărul '''n''', apoi șirul de '''n''' numere naturale, separate prin spații.

== Date de iesire ==

Programul va afișa pe ecran lungimea maximă a secvenței de valori distincte.

== Restrictii si precizari ==

*1 &les; n &les; 1.000.000
*0 &les; a[i] &les; 1.000.000.000

== Exemplul 1 ==
;Intrare
:9
:1 2 1 2 5 6 7 2 9
;Iesire
:Datele introduse corespund restrictiilor impuse
:5

== Exemplul 2 ==
;Intrare
:5
:-10 0 5.2 8 3
;Iesire
:Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def lungime_maxima_secventa_distincte(n, vector):
    frecvente = dict()
    stanga = 0
    lungime_maxima = 0

    for dreapta in range(n):
        numar = vector[dreapta]

        while frecvente.get(numar, 0) > 0:
            frecvente[vector[stanga]] -= 1
            stanga += 1

        frecvente[numar] = 1
        lungime_maxima = max(lungime_maxima, dreapta - stanga + 1)

    return lungime_maxima


def verificare_date_intrare(n, vector):
    if not (1 <= n <= 1000000) or len(vector) != n or not all(0 <= numar <= 1000000000 for numar in vector):
        return False
    return True


# Citire numar de elemente
n = int(input("Introduceți numărul de elemente: "))

# Citire vector
vector = list(map(int, input("Introduceți elementele vectorului, separate prin spațiu: ").split()))

# Verificare date de intrare
if not verificare_date_intrare(n, vector):
    print("Datele introduse nu corespund restricțiilor impuse")
else:
    # Calcul și afișare rezultat
    rezultat = lungime_maxima_secventa_distincte(n, vector)
    print(f"Lungimea maximă a secvenței de valori distincte este: {rezultat}")

</syntaxhighlight>

== Explicatie ==

Secvența de lungime maximă 5 este 1 2 5 6 7.