Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement