Secvențe cu extremități egale

Introducere

Se dă un șir cu n elemente. Să se determine cea mai lungă secvență de elemente din șir cu proprietatea că extremitățile secvenței au valori egale.

Fie V[] vectorul dat, cu n elemente. Vom propune trei soluții, cu diverse complexități.

Soluția 1

Prima soluție are complexitate \( O(n^2) \) și poate fi folosită pentru a rezolva problema #SecvEgale1 .

Considerăm că:

n ≤ 1000
elementele șirului au valori mai mici decât 2³¹

Pentru fiecare element V[i] al vectorului vom determina cel mai mare indice j astfel încât V[i] și V[j] sunt egale. Dintre toate aceste perechi i j o reținem pe aceea pentru care lungimea secvenței, j - i + 1 este mai mare.

Soluția 2

Dacă valorile din șir sunt cuprinse între 1 și vmax, avem o soluție de complexitate \(O(n \cdot vmax)\). Pe site: #Lungime .

Considerăm că:

n ≤ 100000
elementele șirului au valori mai mici sau egale cu vmax=100.

Pentru fiecare valoare c de la 1 la vmax vom determina cel mai din stânga indice i și cel mai din dreapta indice j cu proprietatea că V[i] și V[j] sunt egale cu c. Reținem pereceha i j pentru care j - i + 1 este maxim.

Soluția 3

O soluție de complexitate \(O(n)\) poate fi implementată dacă vmax este suficient de mic pentru a construi un vector cu vmax elemente: #distanta_maxima , #Lungime1 , #SecvEgale1_v2 .

Considerăm că:

n ≤ 100000
elementele șirului au valori mai mici sau egale cu vmax=10000.

Considerăm un vector P[] în care P[k] reprezintă cel mai din stânga indice i cu proprietatea că V[i] = k. Inițial toate elementele lui P sunt nule.

Fie lgmax lungimera maximă a unei secvențe care respectă regula. Inițial, lgmax ← 0. Parcugem vectorul V:

dacă P[V[i]] este zero, suntem la prima apariție a valorii curente V[i] în vector, deci cea mai din stânga. Atunci: P[V[i]] ← i.
dacă P[V[i]] nu este zero, atunci valoarea V[i] a mai apărut în vector, la poziția P[V[i]]. Dacă i - P[V[i]] > lgmax, actualizăm lgmax și reținem secvența P[V[i]] i ca fiind secvența rezultat!