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.
https://gist.github.com/jezinka/666182658ca933dc31928a41d432cc17
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:
https://gist.github.com/jezinka/eaaed2eb8e8c3ea8041a49306deb4a84
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:
https://gist.github.com/jezinka/ea40d83447e14713c9e4fd1e9e444b78
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.
https://gist.github.com/jezinka/89be6db2e2e153abe89601566f9fdb88
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:
https://gist.github.com/jezinka/17ade8dae2a318bba550710d3d009d5c
Można by się jeszcze pokusić o sprawdzanie, czy w pierwszym okienku jest 0 i trochę refaktoringu. Finalnie program wygląda tak:
https://gist.github.com/jezinka/450b279358d823e559a775590806d95e
Więcej zadań, które można rozwiązać przy pomocy tej techniki można znaleźć tu: https://www.geeksforgeeks.org/tag/sliding-window/