The input is the fixed 1000-digit decimal string from the problem statement. For a chosen window length \(w\), the task is to find the largest product of \(w\) consecutive digits. In the original Euler instance, \(w = 13\).
Mathematically, we are evaluating a function \(M(w)\) on one fixed digit sequence. The implementations also define sensible boundary behavior: if \(w \le 0\) or \(w\) is longer than the string itself, the returned value is \(0\).
Let the digits be \(d_0, d_1, \dots, d_{m-1}\), where each \(d_i \in \{0,1,\dots,9\}\) and \(m=1000\) for the Euler input.
For every valid starting position \(i\), define the window product
$$P_i=\prod_{t=0}^{w-1} d_{i+t}, \qquad 0 \le i \le m-w.$$
The desired value is therefore
$$M(w)=\max_{0 \le i \le m-w} P_i.$$
This formula already explains why a complete scan is correct: every block of \(w\) consecutive digits appears exactly once as one of these windows, so taking the maximum over all valid starts cannot miss the optimum.
Because all digits are nonnegative, a zero destroys the whole product of any window that touches it. If the string is decomposed into maximal zero-free runs \(R_1,\dots,R_s\), and a typical run is written as \(R_j=(e_0,e_1,\dots,e_{r_j-1})\), then every window either lies completely inside one run or has product \(0\).
That lets us rewrite the problem as
$$M(w)=\max\left(0,\max_j M_j(w)\right), \qquad M_j(w)=\max_{0 \le i \le r_j-w}\prod_{t=0}^{w-1} e_{i+t},$$
where a run contributes only when \(r_j \ge w\). This is the key structural fact of Problem 8: zeros do not merely lower a candidate product, they partition the whole search into independent nonzero segments plus the fallback value \(0\).
Inside a run with no zeros, consecutive window products satisfy an exact recurrence. If
$$P_i=\prod_{t=0}^{w-1} e_{i+t},$$
then for \(0 \le i < r_j-w\),
$$P_{i+1}=P_i \cdot \frac{e_{i+w}}{e_i}.$$
This identity is valid precisely because \(e_i \neq 0\). It is the natural mathematical basis for a rolling-product or sliding-window optimization. The provided implementations do not use this recurrence; they recompute each \(P_i\) from scratch. That choice keeps the code simple and avoids special zero bookkeeping, which is perfectly reasonable for a 1000-digit input.
For the short sequence \(123456789\) with \(w=2\), the window products are
$$2, 6, 12, 20, 30, 42, 56, 72,$$
so the maximum is \(72\), attained by the final window \(89\).
For the 1000-digit Euler string with \(w=4\), one verified optimal block is \(9989\), giving
$$9 \times 9 \times 8 \times 9 = 5832.$$
For the original target \(w=13\), the maximizing block is \(5576689664895\), and its product is
$$5 \times 5 \times 7 \times 6 \times 6 \times 8 \times 9 \times 6 \times 6 \times 4 \times 8 \times 9 \times 5 = 23514624000.$$
The largest possible product of 13 decimal digits is \(9^{13}=2541865828329\), well below the range of signed 64-bit integers. So there is no overflow problem for the Euler parameter.
There are exactly \(1000-13+1=988\) candidate windows, and the straightforward method performs \(13\) digit multiplications per window. That is only
$$988 \times 13 = 12844$$
digit multiplications, plus trivial loop overhead. For such a small fixed workload, the simpler \(O(mw)\) scan is mathematically transparent and practically fast.
The C++, Python, and Java implementations store the 1000-digit number as one immutable string literal. They all accept a window length parameter, and they all return \(0\) immediately when the requested window is nonpositive or longer than the digit string.
The implementation then loops over every legal starting position \(i\). For each start, it initializes a product accumulator to \(1\), multiplies the \(w\) digits in positions \(i,i+1,\dots,i+w-1\), and compares that product with the best value seen so far.
In other words, the outer loop enumerates the windows from the formula for \(M(w)\), and the inner loop reconstructs the invariant “the accumulator equals the product of the current window” from scratch each time.
All three versions implement the same mathematics. The C++ and Java versions use 64-bit integer arithmetic; Python integers are arbitrary precision, so the same computation is still exact. The code also includes the same two checkpoints in every language: the toy case \((123456789, 2) \mapsto 72\), and the 1000-digit check with \(w=4\) giving \(5832\).
For a digit string of length \(m\), there are \(m-w+1\) windows, and each one is recomputed using \(w\) multiplications. The running time is therefore
$$O((m-w+1)w)=O(mw).$$
The memory usage is \(O(1)\) beyond the stored digit string and a few scalar variables.
For the Euler input with \(m=1000\) and \(w=13\), this means 988 window evaluations and 12,844 digit multiplications. A rolling-product implementation on zero-free runs could reduce the time to \(O(m)\), but the current exhaustive scan is already more than sufficient.
Gegeben ist die feste 1000-stellige Dezimalfolge aus der Aufgabenstellung. Für eine gewählte Fensterlänge \(w\) soll das größte Produkt von \(w\) aufeinanderfolgenden Ziffern bestimmt werden. Im ursprünglichen Euler-Fall ist \(w=13\).
Mathematisch werten wir also eine Funktion \(M(w)\) auf einer festen Ziffernfolge aus. Die Implementierungen behandeln auch Randfälle explizit: Falls \(w \le 0\) oder \(w\) länger als die gesamte Zeichenkette ist, wird \(0\) zurückgegeben.
Bezeichne die Ziffern mit \(d_0, d_1, \dots, d_{m-1}\), wobei \(d_i \in \{0,1,\dots,9\}\) und für die Euler-Eingabe \(m=1000\) gilt.
Für jede zulässige Startposition \(i\) definieren wir das Fensterprodukt
$$P_i=\prod_{t=0}^{w-1} d_{i+t}, \qquad 0 \le i \le m-w.$$
Gesucht ist also
$$M(w)=\max_{0 \le i \le m-w} P_i.$$
Damit ist die Korrektheit des vollständigen Durchlaufs schon erklärt: Jeder Block aus \(w\) aufeinanderfolgenden Ziffern erscheint genau einmal als ein solches Fenster, also kann das Maximum über alle gültigen Startpositionen das Optimum nicht verfehlen.
Da alle Ziffern nichtnegativ sind, vernichtet eine Null das gesamte Produkt jedes Fensters, das sie enthält. Zerlegt man die Folge in maximale nullfreie Abschnitte \(R_1,\dots,R_s\), und schreibt einen solchen Abschnitt als \(R_j=(e_0,e_1,\dots,e_{r_j-1})\), dann liegt jedes Fenster entweder vollständig in einem dieser Abschnitte oder hat Produkt \(0\).
Damit kann man die Aufgabe umformulieren zu
$$M(w)=\max\left(0,\max_j M_j(w)\right), \qquad M_j(w)=\max_{0 \le i \le r_j-w}\prod_{t=0}^{w-1} e_{i+t},$$
wobei ein Abschnitt nur dann beiträgt, wenn \(r_j \ge w\) ist. Das ist die zentrale Struktur von Problem 8: Nullen verschlechtern nicht nur einzelne Kandidaten, sondern teilen die gesamte Suche in voneinander unabhängige nullfreie Teilprobleme plus den Vergleichswert \(0\).
Innerhalb eines Abschnitts ohne Null gilt für benachbarte Fenster eine exakte Rekursion. Wenn
$$P_i=\prod_{t=0}^{w-1} e_{i+t},$$
dann folgt für \(0 \le i < r_j-w\)
$$P_{i+1}=P_i \cdot \frac{e_{i+w}}{e_i}.$$
Diese Identität ist genau deshalb gültig, weil \(e_i \neq 0\) ist. Sie ist die mathematische Grundlage einer Rolling-Product- oder Sliding-Window-Optimierung. Die vorliegenden Implementierungen verwenden diese Rekursion nicht; sie berechnen jedes \(P_i\) neu. Für eine Eingabe mit nur 1000 Ziffern ist das eine saubere und völlig ausreichende Entscheidung.
Für die kurze Folge \(123456789\) mit \(w=2\) lauten die Fensterprodukte
$$2, 6, 12, 20, 30, 42, 56, 72,$$
also ist das Maximum \(72\), erreicht durch das letzte Fenster \(89\).
Für die 1000-stellige Euler-Folge und \(w=4\) ist ein verifizierter optimaler Block \(9989\) mit
$$9 \times 9 \times 8 \times 9 = 5832.$$
Für den eigentlichen Zielwert \(w=13\) ist der maximierende Block \(5576689664895\), und sein Produkt ist
$$5 \times 5 \times 7 \times 6 \times 6 \times 8 \times 9 \times 6 \times 6 \times 4 \times 8 \times 9 \times 5 = 23514624000.$$
Das größtmögliche Produkt von 13 Dezimalziffern ist \(9^{13}=2541865828329\) und liegt damit weit unterhalb des Bereichs vorzeichenbehafteter 64-Bit-Ganzzahlen. Ein Überlaufproblem gibt es für den Euler-Parameter also nicht.
Außerdem gibt es genau \(1000-13+1=988\) Kandidatenfenster, und der direkte Ansatz benötigt \(13\) Ziffernmultiplikationen pro Fenster. Insgesamt sind das nur
$$988 \times 13 = 12844$$
Multiplikationen von Ziffern, zuzüglich vernachlässigbarer Schleifenlogik. Für diese kleine feste Arbeitsmenge ist der einfache \(O(mw)\)-Durchlauf sowohl mathematisch klar als auch praktisch schnell.
Die C++-, Python- und Java-Implementierungen speichern die 1000-stellige Zahl als eine einzige unveränderliche Stringkonstante. Alle drei akzeptieren eine Fensterlänge als Parameter und geben sofort \(0\) zurück, wenn das gewünschte Fenster nicht positiv ist oder länger als die Ziffernfolge.
Danach durchläuft die Implementierung jede zulässige Startposition \(i\). Für jeden Start wird ein Produktakkumulator mit \(1\) initialisiert, anschließend werden die \(w\) Ziffern an den Positionen \(i,i+1,\dots,i+w-1\) multipliziert und das Ergebnis mit dem bisher besten Wert verglichen.
Anders gesagt: Die äußere Schleife enumeriert die Fenster aus der Formel für \(M(w)\), und die innere Schleife stellt die Invariante „der Akkumulator ist genau das Produkt des aktuellen Fensters“ jedes Mal neu her.
Alle drei Sprachversionen setzen dieselbe Mathematik um. C++ und Java verwenden 64-Bit-Ganzzahlen; Python arbeitet mit beliebig großen Ganzzahlen, sodass dieselbe Rechnung ebenfalls exakt bleibt. Außerdem tauchen in allen drei Sprachen dieselben Prüffälle auf: der kleine Test \((123456789, 2) \mapsto 72\) und die 1000-stellige Kontrolle mit \(w=4\), die \(5832\) liefert.
Bei einer Ziffernfolge der Länge \(m\) gibt es \(m-w+1\) Fenster, und jedes wird mit \(w\) Multiplikationen neu berechnet. Die Laufzeit ist also
$$O((m-w+1)w)=O(mw).$$
Der zusätzliche Speicherbedarf ist \(O(1)\) über der gespeicherten Ziffernfolge und einigen Skalarvariablen.
Für die Euler-Eingabe mit \(m=1000\) und \(w=13\) bedeutet das 988 Fensterauswertungen und 12.844 Ziffernmultiplikationen. Eine Rolling-Product-Variante auf nullfreien Abschnitten könnte die Zeit auf \(O(m)\) drücken, aber der vorhandene vollständige Scan ist bereits mehr als ausreichend.
Girdi, soruda verilen sabit 1000 basamaklı onluk dizidir. Seçilen bir pencere uzunluğu \(w\) için amaç, ardışık \(w\) basamağın çarpımının alabileceği en büyük değeri bulmaktır. Asıl Euler örneğinde \(w=13\) alınır.
Dolayısıyla matematiksel olarak sabit bir rakam dizisi üzerinde \(M(w)\) adlı bir fonksiyonu hesaplıyoruz. Uygulamalar sınır durumlarını da açıkça tanımlar: \(w \le 0\) ise veya pencere uzunluğu dizinin kendisinden uzunsa sonuç \(0\) olur.
Basamakları \(d_0, d_1, \dots, d_{m-1}\) ile gösterelim. Burada her \(d_i \in \{0,1,\dots,9\}\) ve Euler girdisi için \(m=1000\) olur.
Geçerli her başlangıç konumu \(i\) için pencere çarpımını
$$P_i=\prod_{t=0}^{w-1} d_{i+t}, \qquad 0 \le i \le m-w$$
diye tanımlayalım. Aradığımız değer o halde
$$M(w)=\max_{0 \le i \le m-w} P_i$$
olur. Bu formül, neden tam taramanın doğru olduğunu da açıklar: uzunluğu \(w\) olan her ardışık blok bu pencerelerden tam birine karşılık gelir. Dolayısıyla tüm geçerli başlangıçlar üzerinde maksimum almak optimumu kaçırmaz.
Tüm basamaklar negatif olmayan sayılar olduğu için bir sıfır, onu içeren her pencerenin çarpımını tamamen yok eder. Dizi, en büyük sıfırsız parçalar \(R_1,\dots,R_s\) biçiminde ayrıştırılsın; tipik bir parçayı da \(R_j=(e_0,e_1,\dots,e_{r_j-1})\) diye yazalım. O zaman her pencere ya bütünüyle bu parçalardan birinin içindedir ya da çarpımı \(0\) olur.
Böylece problem
$$M(w)=\max\left(0,\max_j M_j(w)\right), \qquad M_j(w)=\max_{0 \le i \le r_j-w}\prod_{t=0}^{w-1} e_{i+t}$$
şeklinde yeniden yazılabilir. Burada bir parça ancak \(r_j \ge w\) ise katkı verir. Problem 8'in gerçek yapısı budur: sıfırlar yalnızca bazı adayları küçültmez, aramayı birbirinden bağımsız sıfırsız segmentlere ve yedek değer olarak \(0\)'a böler.
Sıfır içermeyen bir parçada komşu pencere çarpımları tam bir bağıntı sağlar. Eğer
$$P_i=\prod_{t=0}^{w-1} e_{i+t}$$
ise, \(0 \le i < r_j-w\) için
$$P_{i+1}=P_i \cdot \frac{e_{i+w}}{e_i}$$
elde edilir. Bu özdeşlik tam olarak \(e_i \neq 0\) olduğu için geçerlidir. Kayan çarpım ya da sliding-window optimizasyonunun doğal matematiksel temeli budur. Verilen uygulamalar bu bağıntıyı kullanmaz; her \(P_i\) değerini baştan kurar. 1000 basamaklık bir girdi için bu tercih hem sade hem de fazlasıyla yeterlidir.
\(123456789\) dizisi ve \(w=2\) için pencere çarpımları
$$2, 6, 12, 20, 30, 42, 56, 72$$
olur; dolayısıyla maksimum değer son pencere \(89\) ile gelen \(72\)'dir.
1000 basamaklı Euler dizisinde \(w=4\) için doğrulanmış en iyi bloklardan biri \(9989\)'dur ve
$$9 \times 9 \times 8 \times 9 = 5832$$
sonucunu verir.
Asıl hedef olan \(w=13\) durumunda maksimumu veren blok \(5576689664895\) olup çarpımı
$$5 \times 5 \times 7 \times 6 \times 6 \times 8 \times 9 \times 6 \times 6 \times 4 \times 8 \times 9 \times 5 = 23514624000$$
şeklindedir.
13 onluk basamağın alabileceği en büyük çarpım \(9^{13}=2541865828329\) olur; bu değer 64 bit işaretli tamsayı aralığının oldukça altındadır. Yani Euler parametresi için taşma riski yoktur.
Ayrıca tam olarak \(1000-13+1=988\) aday pencere vardır ve doğrudan yöntem pencere başına \(13\) çarpma yapar. Toplam iş yükü yalnızca
$$988 \times 13 = 12844$$
adet basamak çarpımıdır. Bu kadar küçük sabit bir iş için daha sade olan \(O(mw)\) tarama hem matematiksel olarak açıktır hem de pratikte çok hızlıdır.
C++, Python ve Java uygulamaları 1000 basamaklı sayıyı tek bir değiştirilemez string sabiti olarak tutar. Üçü de pencere uzunluğunu parametre olarak alır ve istenen pencere pozitif değilse ya da dizi uzunluğunu aşıyorsa hemen \(0\) döndürür.
Daha sonra uygulama geçerli her başlangıç konumu \(i\) üzerinde döner. Her başlangıç için çarpım değişkeni \(1\) ile başlatılır, \(i,i+1,\dots,i+w-1\) konumlarındaki \(w\) basamak çarpılır ve ortaya çıkan değer o ana kadarki en iyi sonuçla karşılaştırılır.
Başka bir deyişle, dış döngü \(M(w)\) formülündeki pencereleri tek tek listeler; iç döngü ise “elde tutulan çarpım güncel pencerenin çarpımıdır” değişmezini her defasında sıfırdan kurar.
Üç dilde de aynı matematik uygulanır. C++ ve Java 64 bit tamsayı kullanır; Python'da tamsayılar keyfi büyüklükte olduğu için aynı hesap orada da tamdır. Ayrıca üç sürümde aynı iki kontrol bulunur: küçük örnek \((123456789, 2) \mapsto 72\) ve 1000 basamaklı dizide \(w=4\) için \(5832\) doğrulaması.
Uzunluğu \(m\) olan bir basamak dizisi için \(m-w+1\) pencere vardır ve her biri \(w\) çarpma ile yeniden hesaplanır. Bu nedenle süre
$$O((m-w+1)w)=O(mw)$$
olur. Saklanan dizi dışında kullanılan ek bellek ise \(O(1)\)'dir.
Euler girdisinde \(m=1000\) ve \(w=13\) olduğundan 988 pencere değerlendirilir ve 12.844 basamak çarpımı yapılır. Sıfırsız segmentlerde kayan çarpım ile süre \(O(m)\)'ye indirilebilirdi; ancak mevcut tam tarama zaten fazlasıyla yeterlidir.
La entrada es la cadena decimal fija de 1000 dígitos dada en el enunciado. Para una longitud de ventana \(w\), hay que encontrar el mayor producto de \(w\) dígitos consecutivos. En la versión original de Euler se toma \(w=13\).
En términos matemáticos, estamos evaluando una función \(M(w)\) sobre una única secuencia fija de dígitos. Las implementaciones también fijan el comportamiento en los bordes: si \(w \le 0\) o si \(w\) supera la longitud de la cadena, la respuesta devuelta es \(0\).
Denotemos los dígitos por \(d_0, d_1, \dots, d_{m-1}\), con \(d_i \in \{0,1,\dots,9\}\). Para la entrada de Euler, \(m=1000\).
Para cada posición inicial válida \(i\), definimos el producto de ventana
$$P_i=\prod_{t=0}^{w-1} d_{i+t}, \qquad 0 \le i \le m-w.$$
Entonces el valor buscado es
$$M(w)=\max_{0 \le i \le m-w} P_i.$$
Esta expresión ya justifica la corrección del recorrido completo: cada bloque de \(w\) dígitos consecutivos aparece exactamente una vez como una de estas ventanas, así que tomar el máximo sobre todos los comienzos posibles no puede perder el óptimo.
Como todos los dígitos son no negativos, un cero anula por completo el producto de cualquier ventana que lo contenga. Si se descompone la cadena en tramos máximos sin ceros \(R_1,\dots,R_s\), y un tramo típico se escribe como \(R_j=(e_0,e_1,\dots,e_{r_j-1})\), entonces toda ventana o bien queda completamente dentro de uno de esos tramos o bien tiene producto \(0\).
Eso permite reescribir el problema como
$$M(w)=\max\left(0,\max_j M_j(w)\right), \qquad M_j(w)=\max_{0 \le i \le r_j-w}\prod_{t=0}^{w-1} e_{i+t},$$
donde un tramo solo aporta si \(r_j \ge w\). Esta es la estructura específica de Problem 8: los ceros no solo empeoran algunos candidatos, sino que parten la búsqueda en segmentos no nulos independientes y el valor base \(0\).
Dentro de un tramo sin ceros, los productos de ventanas vecinas satisfacen una recurrencia exacta. Si
$$P_i=\prod_{t=0}^{w-1} e_{i+t},$$
entonces para \(0 \le i < r_j-w\) se cumple
$$P_{i+1}=P_i \cdot \frac{e_{i+w}}{e_i}.$$
La identidad es válida precisamente porque \(e_i \neq 0\). Esa es la base matemática natural de una optimización de producto rodante o ventana deslizante. Las implementaciones proporcionadas no usan esta recurrencia; recalculan cada \(P_i\) desde cero. Para una entrada de solo 1000 dígitos, esa decisión mantiene el código simple y sigue siendo totalmente suficiente.
Para la secuencia \(123456789\) con \(w=2\), los productos de ventana son
$$2, 6, 12, 20, 30, 42, 56, 72,$$
así que el máximo es \(72\), alcanzado por la ventana final \(89\).
En la cadena de 1000 dígitos, para \(w=4\), uno de los bloques óptimos verificados es \(9989\), con
$$9 \times 9 \times 8 \times 9 = 5832.$$
Para el objetivo original \(w=13\), el bloque que maximiza el producto es \(5576689664895\), y su valor es
$$5 \times 5 \times 7 \times 6 \times 6 \times 8 \times 9 \times 6 \times 6 \times 4 \times 8 \times 9 \times 5 = 23514624000.$$
El mayor producto posible de 13 dígitos decimales es \(9^{13}=2541865828329\), muy por debajo del rango de un entero con signo de 64 bits. Por tanto, no existe riesgo de desbordamiento para el parámetro de Euler.
Además, hay exactamente \(1000-13+1=988\) ventanas candidatas, y el método directo hace \(13\) multiplicaciones de dígitos por ventana. En total son solo
$$988 \times 13 = 12844$$
multiplicaciones de dígitos, más un coste de bucles despreciable. Con una carga fija tan pequeña, el barrido simple \(O(mw)\) es matemáticamente claro y prácticamente inmediato.
Las implementaciones en C++, Python y Java almacenan el número de 1000 dígitos como una única cadena inmutable. Las tres reciben una longitud de ventana y devuelven \(0\) inmediatamente si la ventana pedida no es positiva o si supera la longitud de la cadena.
Después, la implementación recorre cada posición inicial legal \(i\). Para cada comienzo, inicializa un acumulador de producto con \(1\), multiplica los \(w\) dígitos situados en \(i,i+1,\dots,i+w-1\) y compara el resultado con el mejor valor encontrado hasta ese momento.
Dicho de otra forma: el bucle externo enumera las ventanas de la fórmula de \(M(w)\), y el bucle interno restablece desde cero el invariante “el acumulador es exactamente el producto de la ventana actual”.
Las tres versiones codifican la misma matemática. C++ y Java usan enteros de 64 bits; Python usa enteros de precisión arbitraria, así que el cálculo sigue siendo exacto. Además, las tres incluyen las mismas dos comprobaciones: el caso pequeño \((123456789, 2) \mapsto 72\) y la verificación de la cadena de 1000 dígitos con \(w=4\), cuyo valor es \(5832\).
Para una cadena de longitud \(m\), existen \(m-w+1\) ventanas y cada una se recalcula con \(w\) multiplicaciones. Por tanto, el tiempo de ejecución es
$$O((m-w+1)w)=O(mw).$$
La memoria adicional es \(O(1)\), aparte de la propia cadena y unas pocas variables escalares.
En la entrada de Euler con \(m=1000\) y \(w=13\), eso significa 988 evaluaciones de ventana y 12.844 multiplicaciones de dígitos. Una variante con producto rodante sobre tramos sin ceros podría bajar a \(O(m)\), pero el escaneo exhaustivo actual ya es sobradamente suficiente.
输入是题目给定的那段固定 1000 位十进制数字串。给定窗口长度 \(w\)，目标是求出连续 \(w\) 个数字的乘积最大能达到多少。原始 Euler 问题取 \(w=13\)。
因此从数学上看，我们是在一条固定数字序列上计算函数 \(M(w)\)。三个实现还统一规定了边界行为：如果 \(w \le 0\)，或者 \(w\) 比整条数字串还长，那么结果直接定义为 \(0\)。
把数字记为 \(d_0, d_1, \dots, d_{m-1}\)，其中每个 \(d_i \in \{0,1,\dots,9\}\)。对 Euler 这道题来说，\(m=1000\)。
对每个合法起点 \(i\)，定义窗口乘积
$$P_i=\prod_{t=0}^{w-1} d_{i+t}, \qquad 0 \le i \le m-w.$$
那么所求值就是
$$M(w)=\max_{0 \le i \le m-w} P_i.$$
这个表达式本身已经说明了为什么完整扫描一定正确：长度为 \(w\) 的每一个连续数字块，都会且只会对应一个这样的起点 \(i\)。因此只要把所有合法窗口都看一遍，就不可能漏掉最优解。
因为所有数字都非负，所以一旦窗口里出现 \(0\)，整个乘积立刻变成 \(0\)。如果把整条数字串按零拆成若干个极大的无零区段 \(R_1,\dots,R_s\)，并把其中一个区段写成 \(R_j=(e_0,e_1,\dots,e_{r_j-1})\)，那么任意一个长度为 \(w\) 的窗口只会出现两种情况：要么完全落在某个无零区段内部，要么它跨过了零，乘积因此为 \(0\)。
这就把问题改写成
$$M(w)=\max\left(0,\max_j M_j(w)\right), \qquad M_j(w)=\max_{0 \le i \le r_j-w}\prod_{t=0}^{w-1} e_{i+t},$$
其中只有当 \(r_j \ge w\) 时，该区段才真正有贡献。Problem 8 的关键对象就在这里：零不是一个普通的小数字，而是把整个搜索拆成若干互不干扰的无零子问题，再和基准值 \(0\) 做一次总比较。
在一个没有零的区段里，相邻窗口的乘积满足精确递推。若
$$P_i=\prod_{t=0}^{w-1} e_{i+t},$$
则对 \(0 \le i < r_j-w\) 有
$$P_{i+1}=P_i \cdot \frac{e_{i+w}}{e_i}.$$
这个恒等式之所以成立，正是因为 \(e_i \neq 0\)。它给出了滑动乘积优化最自然的数学基础：窗口右移一位时，只需“除掉离开的数字，再乘上新进入的数字”。不过给定的实现并没有采用这个递推，而是每次都从 1 开始重新计算当前窗口的乘积。对长度只有 1000 的固定输入来说，这样做更直接，也避免了专门处理零的额外状态。
先看短例子 \(123456789\) 且 \(w=2\)。所有窗口乘积依次是
$$2, 6, 12, 20, 30, 42, 56, 72,$$
所以最大值是 \(72\)，由最后一个窗口 \(89\) 取得。
对题目中的 1000 位数字串，如果取 \(w=4\)，程序中验证过的一个最优块是 \(9989\)，于是
$$9 \times 9 \times 8 \times 9 = 5832.$$
而对原题要求的 \(w=13\)，最大乘积对应的 13 位块是 \(5576689664895\)，其乘积为
$$5 \times 5 \times 7 \times 6 \times 6 \times 8 \times 9 \times 6 \times 6 \times 4 \times 8 \times 9 \times 5 = 23514624000.$$
13 个十进制数字的理论最大乘积是 \(9^{13}=2541865828329\)，远远小于有符号 64 位整数的上界，因此这里不存在溢出压力。
另一方面，候选窗口总数恰好是 \(1000-13+1=988\)，而直接方法对每个窗口只做 \(13\) 次数字乘法。总乘法次数不过
$$988 \times 13 = 12844$$
次，再加上很轻的循环开销。对这样一个极小的固定工作量，简单的 \(O(mw)\) 扫描不仅容易验证，而且实际运行也已经足够快。
C++、Python 和 Java 三个实现都把这 1000 位数字保存成一个不可变字符串常量。它们都接收窗口长度作为参数；如果窗口长度不是正数，或者比整条数字串还长，就立刻返回 \(0\)。
随后，程序枚举每个合法起点 \(i\)。对每个起点，都先把乘积累加器设为 \(1\)，再将位置 \(i,i+1,\dots,i+w-1\) 上的 \(w\) 个数字依次相乘，并把得到的乘积与当前最佳值比较。
换句话说，外层循环负责枚举公式 \(M(w)\) 中的全部窗口，内层循环则在每一次开始时重新建立“当前累加器恰好等于当前窗口乘积”这一不变式。
这三个版本实现的是同一套数学。C++ 和 Java 使用 64 位整数；Python 使用任意精度整数，因此结果同样精确。三种语言还都带有相同的两个校验：小例子 \((123456789, 2) \mapsto 72\)，以及 1000 位数字串在 \(w=4\) 时得到 \(5832\) 的检查。
对长度为 \(m\) 的数字串，一共有 \(m-w+1\) 个窗口，而每个窗口都要用 \(w\) 次乘法重新求值，因此时间复杂度为
$$O((m-w+1)w)=O(mw).$$
除去保存输入字符串本身以及少量标量变量之外，额外空间复杂度是 \(O(1)\)。
在 Euler 这道题中，\(m=1000\)、\(w=13\)，因此一共评估 988 个窗口，执行 12,844 次数字乘法。若在无零区段上使用滚动乘积，时间可以降到 \(O(m)\)；但对当前这个固定规模，现有的完整扫描已经完全足够。
На входе дана фиксированная десятичная строка длины 1000 из условия задачи. Для выбранной длины окна \(w\) нужно найти наибольшее произведение \(w\) подряд идущих цифр. В исходной формулировке Euler берется \(w=13\).
Итак, математически требуется вычислить функцию \(M(w)\) на одной фиксированной последовательности цифр. Реализации также явно задают поведение на границах: если \(w \le 0\) или окно длиннее всей строки, возвращается \(0\).
Обозначим цифры через \(d_0, d_1, \dots, d_{m-1}\), где \(d_i \in \{0,1,\dots,9\}\). Для входа Euler имеем \(m=1000\).
Для каждой допустимой стартовой позиции \(i\) определим произведение окна
$$P_i=\prod_{t=0}^{w-1} d_{i+t}, \qquad 0 \le i \le m-w.$$
Тогда искомое значение равно
$$M(w)=\max_{0 \le i \le m-w} P_i.$$
Эта запись сразу объясняет корректность полного перебора: каждый блок из \(w\) последовательных цифр появляется ровно один раз как одно из таких окон, поэтому максимум по всем допустимым началам не может пропустить лучший вариант.
Так как все цифры неотрицательны, один ноль полностью обнуляет произведение любого окна, которое его содержит. Если разбить строку на максимальные участки без нулей \(R_1,\dots,R_s\), а типичный участок записать как \(R_j=(e_0,e_1,\dots,e_{r_j-1})\), то любое окно либо целиком лежит внутри одного такого участка, либо имеет произведение \(0\).
Поэтому задачу можно переписать в виде
$$M(w)=\max\left(0,\max_j M_j(w)\right), \qquad M_j(w)=\max_{0 \le i \le r_j-w}\prod_{t=0}^{w-1} e_{i+t},$$
где участок вносит вклад только при \(r_j \ge w\). Это и есть важнейшая структура Problem 8: нули не просто ухудшают отдельные кандидаты, а делят весь поиск на независимые ненулевые сегменты плюс базовое значение \(0\).
Внутри участка без нулей произведения соседних окон связаны точной рекуррентной формулой. Если
$$P_i=\prod_{t=0}^{w-1} e_{i+t},$$
то для \(0 \le i < r_j-w\) выполняется
$$P_{i+1}=P_i \cdot \frac{e_{i+w}}{e_i}.$$
Эта формула верна именно потому, что \(e_i \neq 0\). Она дает естественную математическую основу для оптимизации со скользящим произведением. Однако предоставленные реализации не используют эту рекурсию; они пересчитывают каждое \(P_i\) заново. Для строки длины 1000 это разумный выбор: код получается проще, а времени все равно достаточно.
Для последовательности \(123456789\) при \(w=2\) оконные произведения равны
$$2, 6, 12, 20, 30, 42, 56, 72,$$
поэтому максимум равен \(72\) и достигается на последнем окне \(89\).
Для 1000-значной строки из задачи при \(w=4\) одним из проверенных оптимальных блоков является \(9989\), и тогда
$$9 \times 9 \times 8 \times 9 = 5832.$$
Для исходного параметра \(w=13\) максимизирующий блок равен \(5576689664895\), а его произведение равно
$$5 \times 5 \times 7 \times 6 \times 6 \times 8 \times 9 \times 6 \times 6 \times 4 \times 8 \times 9 \times 5 = 23514624000.$$
Наибольшее возможное произведение 13 десятичных цифр равно \(9^{13}=2541865828329\), что намного меньше предела знакового 64-битного целого. Значит, для параметра Euler переполнение не грозит.
Кроме того, существует ровно \(1000-13+1=988\) кандидатных окон, а прямой способ выполняет \(13\) умножений цифр на окно. Это всего лишь
$$988 \times 13 = 12844$$
умножений цифр, не считая ничтожных накладных расходов циклов. Для такой маленькой фиксированной нагрузки простой проход за \(O(mw)\) и математически прозрачен, и практически быстр.
Реализации на C++, Python и Java хранят 1000-значное число как одну неизменяемую строковую константу. Все три принимают длину окна как параметр и сразу возвращают \(0\), если окно неположительно или длиннее самой строки.
Далее программа перебирает каждую допустимую стартовую позицию \(i\). Для каждого старта она инициализирует накопитель произведения единицей, перемножает \(w\) цифр на позициях \(i,i+1,\dots,i+w-1\), а затем сравнивает полученное значение с лучшим найденным ранее.
Иными словами, внешний цикл перечисляет окна из формулы для \(M(w)\), а внутренний цикл каждый раз заново восстанавливает инвариант: «накопитель равен произведению текущего окна».
Во всех трех языках используется одна и та же математика. C++ и Java опираются на 64-битные целые; Python использует целые произвольной точности, поэтому результат остается точным. Кроме того, во всех версиях присутствуют одни и те же две проверки: малый пример \((123456789, 2) \mapsto 72\) и контроль для 1000-значной строки при \(w=4\), дающий \(5832\).
Для строки длины \(m\) имеется \(m-w+1\) окон, и каждое пересчитывается с помощью \(w\) умножений. Следовательно, время работы равно
$$O((m-w+1)w)=O(mw).$$
Дополнительная память составляет \(O(1)\), если не считать самой строки и нескольких скалярных переменных.
Для входа Euler при \(m=1000\) и \(w=13\) это означает 988 проверок окон и 12 844 умножения цифр. Вариант со скользящим произведением на безнулевых участках мог бы дать \(O(m)\), но существующий полный перебор уже более чем достаточен.
المعطى هو السلسلة العشرية الثابتة ذات الألف رقم الواردة في نص المسألة. ولطول نافذة \(w\)، نريد إيجاد أكبر حاصل ضرب لـ \(w\) أرقام متتالية. في نسخة Euler الأصلية نأخذ \(w=13\).
وبصياغة رياضية، نحن نحسب دالة \(M(w)\) على تسلسل رقمي ثابت واحد. كما أن التطبيقات تحدد الحالات الحدية بوضوح: إذا كان \(w \le 0\) أو كان أطول من السلسلة كلها، فإن القيمة المعادة هي \(0\).
لنرمز إلى الأرقام بالرموز \(d_0, d_1, \dots, d_{m-1}\)، حيث كل \(d_i \in \{0,1,\dots,9\}\). وفي مدخل Euler لدينا \(m=1000\).
لكل موضع بداية صالح \(i\)، نعرّف حاصل ضرب النافذة بـ
$$P_i=\prod_{t=0}^{w-1} d_{i+t}, \qquad 0 \le i \le m-w.$$
وعندئذ تكون القيمة المطلوبة هي
$$M(w)=\max_{0 \le i \le m-w} P_i.$$
وهذه الصيغة تشرح صحة الفحص الكامل مباشرة: فكل كتلة من \(w\) أرقام متجاورة تظهر مرة واحدة بالضبط كإحدى هذه النوافذ، ولذلك فإن أخذ القيمة العظمى على جميع بدايات النوافذ الصالحة لا يمكن أن يفوّت الحل الأمثل.
بما أن جميع الأرقام غير سالبة، فإن الصفر الواحد يصفر حاصل ضرب أي نافذة تحتويه. وإذا قسّمنا السلسلة إلى مقاطع عظمى خالية من الصفر \(R_1,\dots,R_s\)، وكتبنا مقطعًا نموذجيًا على صورة \(R_j=(e_0,e_1,\dots,e_{r_j-1})\)، فإن كل نافذة تكون إما محصورة بالكامل داخل أحد هذه المقاطع، أو يكون حاصل ضربها \(0\).
وعليه يمكن إعادة كتابة المسألة على النحو
$$M(w)=\max\left(0,\max_j M_j(w)\right), \qquad M_j(w)=\max_{0 \le i \le r_j-w}\prod_{t=0}^{w-1} e_{i+t}.$$
ولا يساهم مقطع ما إلا إذا كان \(r_j \ge w\). وهذه هي البنية الحقيقية في Problem 8: الصفر لا يضعف بعض المرشحين فقط، بل يجزئ البحث كله إلى مسائل مستقلة على المقاطع الخالية من الصفر، مع القيمة الاحتياطية \(0\).
داخل أي مقطع لا يحتوي على صفر، تحقق نوافذ الجوار علاقة تراجعية دقيقة. فإذا كان
$$P_i=\prod_{t=0}^{w-1} e_{i+t},$$
فعند \(0 \le i < r_j-w\) نحصل على
$$P_{i+1}=P_i \cdot \frac{e_{i+w}}{e_i}.$$
وصحة هذه الهوية تعتمد تمامًا على أن \(e_i \neq 0\). وهي الأساس الرياضي الطبيعي لفكرة حاصل الضرب المتدحرج أو النافذة المنزلقة. لكن التطبيقات المعطاة لا تستخدم هذه العلاقة فعليًا؛ بل تعيد حساب كل \(P_i\) من البداية. وبالنسبة إلى سلسلة طولها 1000 رقم فقط، فهذا الاختيار أبسط ويظل كافيًا تمامًا.
في السلسلة \(123456789\) ومع \(w=2\)، تكون حواصل ضرب النوافذ
$$2, 6, 12, 20, 30, 42, 56, 72,$$
ومن ثم فإن القيمة العظمى هي \(72\)، وتتحقق عند النافذة الأخيرة \(89\).
أما في سلسلة Euler ذات الألف رقم، فإذا أخذنا \(w=4\)، فإن إحدى الكتل المثلى المتحققة هي \(9989\)، وبالتالي
$$9 \times 9 \times 8 \times 9 = 5832.$$
وللقيمة الأصلية \(w=13\)، فإن الكتلة التي تعطي الحد الأقصى هي \(5576689664895\)، وحاصل ضربها يساوي
$$5 \times 5 \times 7 \times 6 \times 6 \times 8 \times 9 \times 6 \times 6 \times 4 \times 8 \times 9 \times 5 = 23514624000.$$
أكبر حاصل ضرب ممكن لثلاثة عشر رقمًا عشريًا هو \(9^{13}=2541865828329\)، وهو أصغر بكثير من حد الأعداد الصحيحة الموقعة ذات 64 بت. لذلك لا توجد مشكلة فيضان عددي في هذه المسألة.
ومن ناحية أخرى، يوجد بالضبط \(1000-13+1=988\) نافذة مرشحة، والطريقة المباشرة تنفذ \(13\) عملية ضرب لكل نافذة. أي إن عدد عمليات ضرب الأرقام لا يتجاوز
$$988 \times 13 = 12844$$
عملية، مع كلفة حلقات بسيطة جدًا. ولهذا فإن المسح المباشر بتعقيد \(O(mw)\) واضح رياضيًا وسريع عمليًا بما يكفي تمامًا.
تخزن تطبيقات C++ وPython وJava العدد ذا الألف رقم كسلسلة ثابتة غير قابلة للتغيير. كما أنها تستقبل طول النافذة كمعامل، وتعيد \(0\) فورًا إذا كان هذا الطول غير موجب أو أطول من السلسلة.
بعد ذلك تمر الشيفرة على كل موضع بداية صالح \(i\). ولكل موضع، تبدأ بمجمّع حاصل ضرب قيمته \(1\)، ثم تضرب الأرقام \(w\) الواقعة في المواقع \(i,i+1,\dots,i+w-1\)، وبعدها تقارن الناتج بأفضل قيمة شوهدت حتى تلك اللحظة.
وبصياغة أخرى: الحلقة الخارجية تعدّد جميع النوافذ التي تظهر في صيغة \(M(w)\)، بينما تعيد الحلقة الداخلية بناء الثابت التالي من الصفر في كل مرة: “المجمّع يساوي تمامًا حاصل ضرب النافذة الحالية”.
النسخ الثلاث تنفذ الرياضيات نفسها. يستخدم C++ وJava أعدادًا صحيحة 64-بت؛ أما Python فيستخدم أعدادًا صحيحة غير محدودة الدقة، ولذلك تبقى النتيجة دقيقة أيضًا. كما أن اللغات الثلاث تتضمن حالتي التحقق نفسيهما: المثال الصغير \((123456789, 2) \mapsto 72\)، والفحص الخاص بالسلسلة ذات الألف رقم عند \(w=4\) والذي يعطي \(5832\).
إذا كان طول السلسلة \(m\)، فعدد النوافذ هو \(m-w+1\)، وكل نافذة يعاد حسابها بواسطة \(w\) عمليات ضرب. لذا يكون تعقيد الزمن
$$O((m-w+1)w)=O(mw).$$
أما الذاكرة الإضافية فهي \(O(1)\)، باستثناء السلسلة نفسها وبعض المتغيرات العددية البسيطة.
في مدخل Euler حيث \(m=1000\) و\(w=13\)، يعني هذا تقييم 988 نافذة وتنفيذ 12,844 عملية ضرب للأرقام. كان من الممكن تخفيض الزمن إلى \(O(m)\) باستعمال حاصل ضرب متدحرج داخل المقاطع الخالية من الصفر، لكن الفحص الكامل الحالي كافٍ تمامًا.