Rozwiązuję sobie ostatnio zadania z Projektu Euler i natrafiłam na zadanie 8, które zainspirowało mnie do tej notki.
Największy iloczyn 13 kolejnych cyfr z 1000 cyfrowej liczby 🙂 Można to zrobić najprościej – pętla po wszystkich cyfrach, a potem branie 13 kolejnych cyfr. Wynik dla 4 kolejnych cyfr, który jest podany w treści zadania wykorzystam jako test sprawdzający.
Niestety, nie optymalne, złożoność czasowa aż O(n*k). Dla 4 liczb mamy 4 * 1000 obrotów w pętli, ale dla 13 to już 13000. A gdyby liczba była 10, 100 razy większa? Musi być inny sposób… I jest.
Window sliding technique – technika przesuwanego okienka. Można to sobie wyobrazić jako kalendarz z przesuwanym na taśmie okienkiem:
Dla uproszczenia skupię się na mniejszym przykładzie i poszukam największej sumy z wymyślonej mniejszej liczby. W tym wypadku okienko będzie mieściło w sobie 4 cyfry.
Algorytm wygląda tak:
- Wyliczamy początkową sumę w okienku (window_sum) – jest ona w tym momencie również maksymalną sumą (max_sum)
- Przesuwamy okienko – wyliczamy kolejną sumę korzystając z poprzednich wyliczeń:
- od window_sum odejmujemy cyfrę, która opuściła okienko
- do window_sum dodajemy cyfrę, która trafiła do okieka
- Jeśli nowa suma jest większa niż max_sum, to za max_sum przypisujemy window_sum
- Jeśli mamy jeszcze jakieś cyfry w “dużej liczbie” to wracamy do punktu 2
W formie graficznej wygląda to mniej więcej tak:
A kod tak:
Tutaj kroków w pętli jest tyle ile wynosi długość “dużej liczby”, czyli złożoność czasowa O(n). Zupełnie nie zależy to od wielkości okienka.
Ok, ale to było dodawanie, a w zadaniu każą znaleźć największy iloczyn.
Niestety nie można po prostu przenieść wersji z dodawaniem na mnożenie:
Bardzo szybko wypadnie error, że nie wolno dzielić przez 0.
Pierwsze zabezpieczenie: sprawdźmy, czy następny element jest równy 0. Jeśli jest to przeskakujemy go i wyliczamy od nowa sumę w okienku.
Prawie dobrze, ale co w wypadku jeśli w nowym okienku znajdzie się 0, a może nawet dwa, więc omińmy je wszystkie:
Można by się jeszcze pokusić o sprawdzanie, czy w pierwszym okienku jest 0 i trochę refaktoringu. Finalnie program wygląda tak:
Więcej zadań, które można rozwiązać przy pomocy tej techniki można znaleźć tu: https://www.geeksforgeeks.org/tag/sliding-window/