Algorytm opiera się na obserwacji, że jeśli liczba x pojawiła się na wejsciu więcej, niż raz, to my jesteśmy zainteresowani jej ostatnim wystąpieniem. Dla przykładu:
7 5 8 9 5 4 4
Liczba 4 pojawiła się dwa razy, ale jej drugie wystąpienie jest dalej od każdej poprzedniej liczby, więc jej pierwsze wystąpienie nas nie interesuje.

1) w tablicy A trzymamy pierwsze wystąpienie liczby z indeksu, tzn A[i] mówi nam o pierwszym wystąpieniu liczby o wartosci i

2) w tablicy B trzymamy ostatnie wystąpienie
3) sumujemy tablice B[1..n] tak, żeby w czasie stalym móc odpowiedzieć na pytanie, jaki jest max w tabllicy B[x..n] dla jakiegos x < n
Robimy to w ten sposób:

template <class T>
void array_part_max (T *Source, size_t size) { // O(n)
	if (size >= 2) {
		for (long long int it = size - 2; it >= 0; --it) {
			if (Source[it] < Source[it+1])
				Source[it] = Source[it+1];
		}
		Source[size] = Source[size-1];
	}
}

Do funkcji przekazujemy tablice B. Funkcja ta w B[x] zapisze max B[x..n]

4) Szukamy max z {B[i+1] - A[i] : 0 < i < maksymalna wprowadzona liczba && liczba i występuje na wejsciu}
5) Odpowiedzią jest para (A[i], B[i+1])

Przykład:
in: 6 4 5 1 3 1
A: -1 3 -1 4 1 2 0 (A[x] = -1 <=> x nie występuje na wejsciu)
B: -1 5 -1 4 1 2 0
B: 5 5 4 4 2 2 2 (po użyciu przedstawionej funkcji)
Szukamy max z {B[i+1] - A[i] : i należy do {1, 3, 4, 5} }, jest nim 2 - 1 = 1 dla i = 4