# PBinfo #4614 – 3secv1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Pentru un șir de n numere, să se găsească lungimea celei mai lungi secvențe care conține maximum 3 numere distincte. Un exemplu de astfel de secvență este: 9 1 0, dar un exemplu de secvență care nu respectă această regulă este 4 2 1 3 4.

Cerința
Dându-se t șiruri a de n numere, să se găsească lungimea celei mai lungi secvențe care conține maximum 3 numere distincte.

Date de intrare
Pe prima linie a fișierului de intrare 3secv.in se află numărul t. Pentru fiecare test, pe prima linie se va afla n, reprezentând numărul de numere. Pe a doua linie se vor afla cele n numere.

Date de ieșire
Fișierul de ieșire 3secv.out va conține t linii, linia i conținând lungimea maximă a unei secvențe de maximum 3 numere distincte pentru cel de-al i-lea șir dat la intrare.

Restricții și precizări

1 ≤ t ≤ 1000
1 ≤ n ≤ 1.000.000
Suma lungimilor celor t șiruri nu depășește 1.000.000.
1 ≤ a[i] ≤ 1.000.000.000

Exemplu:
3secv.in

5
10
1 4 7 4 2 4 7 3 2 3
8
1 2 4 1 5 3 1 2
10
6 8 9 1 8 5 4 6 3 2 
6
1 1 1 2 2 2
12
1 5 8 3 2 5 7 4 9 5 7 4
3secv.out

6
4
4
6
3
Explicație
Secvența 4 7 4 2 4 7 conține 3 numere distincte. Nu mai există nicio secvență de lungime mai mare decât 6.

## Cod sursă C++

```cpp
/*
    Autor problema: Traian Mihai Danciu
    Autor solutie: Stefan Dascalescu
    Timp: O(n)
    Memorie: O(1)
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ifstream fin("3secv.in");
	ofstream fout("3secv.out");
	int t;
	fin >> t;
	for(; t; t--)
	{
		int n;
		fin >> n;
		// dist[i] = care e a i-a valoare distincta
		// lst[i] = unde a aparut ultima oara
		int dist[3];
		int lst[3];
		for(int i = 0; i <= 2; i++)
		{
			dist[i] = -1;
			lst[i] = -1;
		}
		int smallest = 0;
		int ans = 0;
		for(int i = 1; i <= n; i++)
		{
			int x;
			fin >> x;
			bool ok = 0;
			for(int j = 0; j <= 2; j++)
				if(dist[j] == x)
				{
					ok = 1;
					lst[j] = i;
				}
			if(ok == 0)
			{
				for(int j = 0; j <= 2; j++)
					if(dist[j] == -1)
					{
						dist[j] = x;
						lst[j] = i;
						ok = 1;
						break;
					}
				if(ok == 0)
				{
					int smallest_last = 0;
					for(int j = 1; j <= 2; j++)
						if(lst[j] < lst[smallest_last])
							smallest_last = j;
					smallest = lst[smallest_last];
					dist[smallest_last] = x;
					lst[smallest_last] = i;
					ok = 1;
				}
			}
			ans = max(ans, i - smallest);
		}
		fout << ans << '\n';
	}
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4614)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4614/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4614/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)