Editing 0310 - SecvPal

Sursa: [https://www.pbinfo.ro/probleme/310/secvpal  0310 - SecvPal]
----
O secvenţă a unui vector se numeşte palindromică dacă primul element ale secvenţei este egal cu ultimul, al doilea cu penultimul, etc.


== Cerinţa ==
Se dă un vector cu n elemente, numere naturale. Determinaţi secvenţa palindromică de lungime maximă.


== Date de intrare ==
Fişierul de intrare secvpal.in conţine pe prima linie numărul n; urmează cele n elemente ale vectorului, dispuse pe mai multe linii şi separate prin spaţii.


== Date de ieșire == 
Fişierul de ieşire secvpal.out va conţine pe prima linie numerele p şi u, reprezentând indicii de început şi sfârşit ai secvenţei determinate.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 1000;
* numerele de pe a doua linie a fişierului de intrare vor avea cel mult 4 cifre;
* dacă există mai multe secvenţe palindromice de lungime maximă, se va determina cea mai din stânga;
== Exemplu ==
; Intrare
: 12
: 1 2 10 9 8 5 8 9 10 5 5 10
; Ieșire
: 3 9 

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0310 - SecvPal

def citire():
    n = int(input())
    v = []
    for i in range(n):
        v.extend(list(map(int, input().split())))
    return v

def secv_palindrom(v):
    n = len(v)
    max_len = 0
    start = 0
    end = 0
    for i in range(n):
        for j in range(i, n):
            if v[i:j+1] == v[i:j+1][::-1] and j-i+1 > max_len:
                max_len = j-i+1
                start = i
                end = j
    return (start, end)

def validare(v, start, end):
    return v[start:end+1] == v[start:end+1][::-1]

if __name__ == "__main__":
    v = citire()
    (start, end) = secv_palindrom(v)
    if validare(v, start, end):
        print(start, end)
    else:
        print("Eroare: Secventa gasita nu este palindromica.")

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția citire citește vectorul v din input, care conține numerele naturale date pe mai multe linii, separate prin spații.

Funcția secv_palindrom primește ca parametru vectorul v și găsește secvența palindromică de lungime maximă, returnând indicii de început și de sfârșit ai acestei secvențe. Această funcție utilizează o metodă brute-force de căutare a tuturor sub-șirurilor posibile din vector și verificarea lor dacă sunt palindromice.

Funcția validare primește vectorul v și indicii de început și de sfârșit ai secvenței palindromice găsite și verifică dacă această secvență este într-adevăr palindromică.

În funcția main, se apelează funcția citire pentru a citi vectorul v din input, apoi se apelează funcția secv_palindrom pentru a găsi secvența palindromică de lungime maximă și se verifică cu ajutorul funcției validare dacă aceasta este într-adevăr palindromică. Dacă este, se afișează indicii de început și de sfârșit ai secvenței găsite, altfel se afișează un mesaj de eroare.