A \(2000 \times 2000\) table is filled row by row with a pseudo-random sequence \(s_1,s_2,\dots,s_{4{,}000{,}000}\). Among every row, every column, and both diagonal families, we must find the contiguous segment whose sum is as large as possible.
The difficulty is not generating the table; it is that the search space of all contiguous segments is enormous if approached naively. The crucial simplification is that each admissible segment lies on a single one-dimensional line, and each such line can be solved optimally by the standard maximum-subarray recurrence.
Let \(n=2000\). The implementations first generate the centered lagged sequence, reinterpret it as an \(n \times n\) matrix, and then reduce the entire problem to repeated one-dimensional scans.
For \(1 \le k \le 55\), the values are defined by
$$s_k=\left(100003-200003k+300007k^3 \bmod 10^6\right)-500000.$$
For \(56 \le k \le n^2\), the recurrence becomes
$$s_k=\left(s_{k-24}+s_{k-55}+10^6 \bmod 10^6\right)-500000.$$
After the reduction modulo \(10^6\), every entry lies in the interval \([-500000,499999]\). The matrix is then filled in row-major order:
$$A_{i,j}=s_{(i-1)n+j}\qquad (1 \le i,j \le n).$$
So the problem is really about the matrix \(A\), but the generator matters because it tells us there are exactly \(4{,}000{,}000\) values and that each cell can be addressed directly through one linear index.
Any valid subsequence must be contiguous inside one row, one column, one down-right diagonal, or one down-left diagonal. It never bends, branches, or skips entries. That lets us define four line families:
$$R_i=(A_{i,1},A_{i,2},\dots,A_{i,n}),\qquad 1 \le i \le n,$$
$$C_j=(A_{1,j},A_{2,j},\dots,A_{n,j}),\qquad 1 \le j \le n,$$
$$D_p=(A_{i,j}: j-i=p),\qquad -(n-1) \le p \le n-1,$$
$$E_q=(A_{i,j}: i+j=q),\qquad 2 \le q \le 2n.$$
If \(M(L)\) denotes the maximum sum of a contiguous block inside a line \(L\), then the final answer is
$$\max\bigl(\{M(R_i)\}\cup\{M(C_j)\}\cup\{M(D_p)\}\cup\{M(E_q)\}\bigr).$$
The two-dimensional part of the problem is therefore only geometric bookkeeping: identify every relevant line exactly once, then solve the same one-dimensional optimization on each of them.
Take any scanned line \(x_1,x_2,\dots,x_m\). Define \(B_t\) as the maximum sum of a contiguous segment that must end at position \(t\). Then
$$B_1=x_1,\qquad B_t=\max(x_t,\;B_{t-1}+x_t)\quad (t \ge 2).$$
This recurrence is exact because an optimal segment ending at \(t\) has only two possibilities: either it starts fresh at \(t\), or it extends the best segment that already ended at \(t-1\). No third case exists.
If we also define
$$G_t=\max(G_{t-1},B_t),$$
then \(G_t\) is the best contiguous sum seen in the prefix \(x_1,\dots,x_t\). By the time the line is finished, \(G_m=M(L)\). This is Kadane's algorithm in its dynamic-programming form, using only constant extra memory.
Rows and columns are obvious, but the diagonal families need slightly more care. Every down-right diagonal is determined by the difference \(j-i\), so there are \(2n-1\) of them. The implementation starts these lines from the top edge \((1,c)\) for all \(c\), then from the left edge \((r,1)\) for \(r \ge 2\). That lists every constant-\(j-i\) diagonal once, with no duplicate start point.
Similarly, every down-left diagonal is determined by the sum \(i+j\). The implementation starts them from the top edge \((1,c)\) for all \(c\), then from the right edge \((r,n)\) for \(r \ge 2\). Again we get exactly one start point for each diagonal.
The length pattern of either diagonal family is
$$1,2,\dots,n-1,n,n-1,\dots,2,1,$$
whose sum is \(n^2\). So each diagonal family touches exactly \(n^2\) matrix entries in total, just as the row scan and the column scan do.
Suppose one row or diagonal contains the values
$$L=(-8,3,5,-2,4,-10,6,7).$$
Then the best sum ending at each position is
$$B=(-8,3,8,6,10,0,6,13).$$
The interpretation is the whole point of the recurrence. At the sixth entry, for example, the best segment ending there has sum \(0\), because extending the earlier best segment gives \(10-10=0\), which is better than starting a new segment at \(-10\). At the eighth entry, the recurrence reaches \(13\), so the best contiguous block in this line is \(6+7=13\).
The real problem simply repeats this computation across every row, every column, and every diagonal generated from the \(2000 \times 2000\) table.
The C++, Python, and Java implementations first allocate a one-dimensional container of length \(4{,}000{,}001\) so that the lagged sequence can be stored with convenient 1-based indexing. The first 55 terms use the cubic formula, and all later terms use the \((24,55)\)-lag recurrence. Matrix entry \((r,c)\) is then read directly from the row-major position \(rn+c+1\) in zero-based loop coordinates.
After generation, the implementation performs four independent sweeps: all rows, all columns, all down-right diagonals, and all down-left diagonals. Before each new line, it resets the current line-ending optimum to a very negative sentinel, then updates that value with the recurrence \( \max(v,\text{current}+v) \) as each new matrix element \(v\) is visited.
The diagonal loops are written by boundary starts rather than by building explicit diagonal arrays. That keeps the code simple: each line is consumed in place, immediately feeding the maximum-subarray update.
While scanning a line, the implementation also updates a global best value. Once every family has been processed, that global best is exactly the answer, because every admissible contiguous subsequence has appeared in one and only one of those scans.
The three language versions use the same mathematics and the same traversal order; they differ only in syntax and container types.
Let \(n=2000\). Sequence generation costs \(n^2\) updates. The row sweep examines \(n^2\) entries, the column sweep examines another \(n^2\), and the two diagonal families contribute \(n^2\) entries each. So the total work is
$$n^2+n^2+n^2+n^2+n^2=5n^2=20{,}000{,}000$$
basic value updates, which is \(O(n^2)\).
Space usage is \(O(n^2)\) in the given implementations because they store the whole table through the generated sequence. The running state for Kadane's recurrence itself is only \(O(1)\). Also, since each entry is at most \(499999\) and each line has length at most \(2000\), any line sum stays below \(2000 \cdot 499999 < 10^9\), so fixed-width integer arithmetic is sufficient for the compiled versions.
Eine \(2000 \times 2000\)-Tabelle wird zeilenweise mit einer pseudozufälligen Folge \(s_1,s_2,\dots,s_{4{,}000{,}000}\) gefüllt. Unter allen Zeilen, allen Spalten und beiden Diagonalfamilien ist diejenige zusammenhängende Teilfolge gesucht, deren Summe maximal ist.
Die Schwierigkeit liegt nicht in der Erzeugung der Tabelle, sondern in der riesigen Zahl möglicher Teilsegmente. Der entscheidende Schritt ist, dass jede zulässige Teilfolge vollständig auf genau einer eindimensionalen Linie liegt und dass dieses eindimensionale Problem optimal durch dieselbe Rekurrenz gelöst werden kann.
Setze \(n=2000\). Die Implementierungen erzeugen zuerst die zentrierte verzögerte Folge, interpretieren sie dann als \(n \times n\)-Matrix und führen anschließend nur noch eindimensionale Maximum-Teilarray-Scans aus.
Für \(1 \le k \le 55\) gilt
$$s_k=\left(100003-200003k+300007k^3 \bmod 10^6\right)-500000.$$
Für \(56 \le k \le n^2\) lautet die Rekurrenz
$$s_k=\left(s_{k-24}+s_{k-55}+10^6 \bmod 10^6\right)-500000.$$
Nach der Reduktion modulo \(10^6\) liegt jeder Eintrag im Intervall \([-500000,499999]\). Die Matrix wird anschließend in Zeilenreihenfolge befüllt:
$$A_{i,j}=s_{(i-1)n+j}\qquad (1 \le i,j \le n).$$
Damit ist das eigentliche Objekt des Problems die Matrix \(A\), aber der Generator liefert die exakten \(4{,}000{,}000\) Werte und eine direkte lineare Adressierung jeder Zelle.
Jede zulässige Teilfolge ist zusammenhängend innerhalb genau einer Zeile, einer Spalte, einer Diagonale nach rechts unten oder einer Diagonale nach links unten. Sie darf weder abbiegen noch Felder überspringen. Deshalb zerlegt man die Suche in vier Familien:
$$R_i=(A_{i,1},A_{i,2},\dots,A_{i,n}),\qquad 1 \le i \le n,$$
$$C_j=(A_{1,j},A_{2,j},\dots,A_{n,j}),\qquad 1 \le j \le n,$$
$$D_p=(A_{i,j}: j-i=p),\qquad -(n-1) \le p \le n-1,$$
$$E_q=(A_{i,j}: i+j=q),\qquad 2 \le q \le 2n.$$
Bezeichnet \(M(L)\) die maximale Summe eines zusammenhängenden Blocks innerhalb einer Linie \(L\), dann ist die gesuchte Antwort
$$\max\bigl(\{M(R_i)\}\cup\{M(C_j)\}\cup\{M(D_p)\}\cup\{M(E_q)\}\bigr).$$
Der zweidimensionale Teil des Problems ist also nur die saubere Auflistung aller relevanten Linien; die Optimierung selbst bleibt eindimensional.
Betrachte eine beliebige gescannte Linie \(x_1,x_2,\dots,x_m\). Definiere \(B_t\) als die größte Summe eines zusammenhängenden Segments, das zwingend an Position \(t\) endet. Dann gilt
$$B_1=x_1,\qquad B_t=\max(x_t,\;B_{t-1}+x_t)\quad (t \ge 2).$$
Diese Rekurrenz ist vollständig: Ein optimales Segment, das bei \(t\) endet, startet entweder neu bei \(t\), oder es verlängert das beste Segment, das bei \(t-1\) endete. Eine dritte Möglichkeit gibt es nicht.
Mit
$$G_t=\max(G_{t-1},B_t)$$
ist \(G_t\) die beste zusammenhängende Summe im Präfix \(x_1,\dots,x_t\). Am Ende der Linie ist daher \(G_m=M(L)\). Genau das ist Kadanes Algorithmus in dynamischer Programmierungsform mit nur konstantem Zusatzspeicher.
Zeilen und Spalten sind direkt, bei den Diagonalen muss man die Startpunkte sauber wählen. Jede Diagonale nach rechts unten wird durch die Differenz \(j-i\) bestimmt, also gibt es \(2n-1\) Stück. Die Implementierung startet sie an der oberen Kante \((1,c)\) für alle \(c\) und anschließend an der linken Kante \((r,1)\) für \(r \ge 2\). So erscheint jede konstante-\(j-i\)-Diagonale genau einmal.
Jede Diagonale nach links unten wird durch die Summe \(i+j\) bestimmt. Deshalb startet die Implementierung an der oberen Kante \((1,c)\) für alle \(c\) und danach an der rechten Kante \((r,n)\) für \(r \ge 2\). Auch hier entsteht jeder Startpunkt genau einmal.
Die Längen beider Diagonalfamilien folgen dem Muster
$$1,2,\dots,n-1,n,n-1,\dots,2,1,$$
dessen Summe \(n^2\) ist. Jede Diagonalfamilie berührt insgesamt also genau so viele Einträge wie ein kompletter Zeilen- oder Spaltenscan.
Angenommen, eine Zeile oder Diagonale enthält
$$L=(-8,3,5,-2,4,-10,6,7).$$
Dann lauten die besten Summen, die jeweils an der aktuellen Position enden,
$$B=(-8,3,8,6,10,0,6,13).$$
Der inhaltliche Kern steckt in dieser Folge. Beim sechsten Wert etwa ist das beste Segment mit Endpunkt dort nicht \(-10\), sondern die Verlängerung des bisherigen Optimums mit Summe \(10-10=0\). Beim achten Wert erreicht die Rekurrenz \(13\), also ist der beste zusammenhängende Block dieser Linie \(6+7=13\).
Im eigentlichen Problem wird genau dieselbe Rechnung für jede Zeile, jede Spalte und jede Diagonale der \(2000 \times 2000\)-Tabelle wiederholt.
Die C++-, Python- und Java-Implementierungen reservieren zunächst einen eindimensionalen Speicher mit \(4{,}000{,}001\) Positionen, damit die Folge bequem 1-indiziert abgelegt werden kann. Die ersten 55 Terme kommen aus der kubischen Formel, alle späteren aus der Rekurrenz mit den Lags 24 und 55. Ein Matrixwert an \((r,c)\) wird anschließend direkt über die Zeilenreihenfolge adressiert.
Nach der Erzeugung folgen vier unabhängige Durchläufe: alle Zeilen, alle Spalten, alle Diagonalen nach rechts unten und alle Diagonalen nach links unten. Vor jeder neuen Linie setzt die Implementierung die laufende beste Summe mit festem Endpunkt auf einen sehr negativen Startwert zurück und aktualisiert sie dann mit \( \max(v,\text{aktuell}+v) \), sobald der nächste Matrixeintrag \(v\) gelesen wird.
Für Diagonalen werden keine separaten Hilfsarrays aufgebaut. Stattdessen werden die Linien direkt von ihren Randstartpunkten aus abgegangen und sofort an die Maximum-Teilarray-Rekurrenz weitergereicht.
Während des Linien-Scans wird gleichzeitig ein globales Maximum aktualisiert. Nach Abschluss aller vier Familien ist dieser Wert exakt die gesuchte Antwort, denn jede zulässige zusammenhängende Teilfolge wurde genau einmal betrachtet.
Die drei Sprachversionen verwenden dieselbe Mathematik und dieselbe Traversierungslogik; Unterschiede gibt es nur in Syntax und Datentypen.
Für \(n=2000\) kostet die Erzeugung der Folge \(n^2\) Schritte. Der Zeilenscan betrachtet \(n^2\) Einträge, der Spaltenscan weitere \(n^2\), und jede der beiden Diagonalfamilien trägt ebenfalls \(n^2\) Einträge bei. Insgesamt entstehen also
$$n^2+n^2+n^2+n^2+n^2=5n^2=20{,}000{,}000$$
elementare Aktualisierungen, also \(O(n^2)\) Zeit.
Der Speicherverbrauch ist in den gegebenen Implementierungen \(O(n^2)\), weil die gesamte Tabelle über die Folge gespeichert wird. Die eigentliche Kadane-Rekurrenz benötigt nur \(O(1)\) Zusatzspeicher. Da jeder Eintrag höchstens \(499999\) beträgt und jede Linie Länge höchstens \(2000\) hat, bleibt jede Liniensumme unter \(2000 \cdot 499999 < 10^9\); Festkomma-Arithmetik mit festen Ganzzahltypen reicht also aus.
\(2000 \times 2000\) boyutlu bir tablo, \(s_1,s_2,\dots,s_{4{,}000{,}000}\) sözde rastgele dizisiyle satır satır dolduruluyor. Bütün satırlar, bütün sütunlar ve iki köşegen ailesi içinde yer alan bitişik parçalar arasında toplamı en büyük olanı bulmamız isteniyor.
Asıl zorluk tabloyu üretmek değil, olası bütün bitişik parçaları kaba kuvvetle denemenin aşırı pahalı olmasıdır. Çözümün ana fikri, her geçerli alt dizinin tek bir doğrultu üzerinde yatması ve her böyle tek boyutlu doğrunun aynı maksimum alt dizi bağıntısıyla en iyi biçimde çözülebilmesidir.
\(n=2000\) olsun. Uygulamalar önce merkezlenmiş gecikmeli diziyi üretir, sonra bunu \(n \times n\) matris olarak yorumlar ve en sonunda işi art arda yapılan tek boyutlu taramalara indirger.
\(1 \le k \le 55\) için
$$s_k=\left(100003-200003k+300007k^3 \bmod 10^6\right)-500000$$
tanımı kullanılır. \(56 \le k \le n^2\) için ise
$$s_k=\left(s_{k-24}+s_{k-55}+10^6 \bmod 10^6\right)-500000$$
bağıntısı geçerlidir. Mod \(10^6\) işleminden sonra her terim \([-500000,499999]\) aralığındadır. Bu değerler matrise satır-major biçimde yerleştirilir:
$$A_{i,j}=s_{(i-1)n+j}\qquad (1 \le i,j \le n).$$
Dolayısıyla problemde aradığımız gerçek nesne \(A\) matrisidir; ancak üreteç hem tam olarak \(4{,}000{,}000\) değer oluşturduğumuzu hem de her hücreye tek bir doğrusal indisle erişebildiğimizi açıklar.
Geçerli her alt dizi, tek bir satır, tek bir sütun, sağ aşağı yönlü bir köşegen ya da sol aşağı yönlü bir köşegen üzerinde bitişik olmak zorundadır. Yol kıramaz, dallanamaz, aradan eleman atlayamaz. Bu yüzden arama dört aileye ayrılır:
$$R_i=(A_{i,1},A_{i,2},\dots,A_{i,n}),\qquad 1 \le i \le n,$$
$$C_j=(A_{1,j},A_{2,j},\dots,A_{n,j}),\qquad 1 \le j \le n,$$
$$D_p=(A_{i,j}: j-i=p),\qquad -(n-1) \le p \le n-1,$$
$$E_q=(A_{i,j}: i+j=q),\qquad 2 \le q \le 2n.$$
Burada \(M(L)\), bir \(L\) doğrusu içindeki en büyük bitişik blok toplamı olsun. O zaman cevap
$$\max\bigl(\{M(R_i)\}\cup\{M(C_j)\}\cup\{M(D_p)\}\cup\{M(E_q)\}\bigr)$$
olur. Yani problemin iki boyutlu kısmı yalnızca hangi doğruların taranacağını belirlemektir; optimizasyonun kendisi hep tek boyutludur.
Taranan herhangi bir doğruyu \(x_1,x_2,\dots,x_m\) biçiminde yazalım. \(B_t\), mutlaka \(t\) konumunda biten en büyük bitişik toplam olsun. O halde
$$B_1=x_1,\qquad B_t=\max(x_t,\;B_{t-1}+x_t)\quad (t \ge 2).$$
Bu bağıntı eksiksizdir; çünkü \(t\)'de biten en iyi parça ya doğrudan \(t\)'de başlar ya da \(t-1\)'de biten en iyi parçanın uzatılmasıdır. Başka bir olasılık yoktur.
Ayrıca
$$G_t=\max(G_{t-1},B_t)$$
tanımlanırsa \(G_t\), \(x_1,\dots,x_t\) ön ekinde şimdiye kadar görülen en büyük bitişik toplam olur. Doğrunun sonunda \(G_m=M(L)\) elde edilir. Bu, Kadane algoritmasının dinamik programlama biçimidir ve yalnızca sabit ek bellek kullanır.
Satırlar ve sütunlar açık; asıl dikkat köşegenlerde gerekir. Sağ aşağı köşegenler \(j-i\) farkıyla belirlenir, dolayısıyla toplam \(2n-1\) tanedir. Uygulama bunları önce üst kenardaki \((1,c)\) başlangıçlarından, sonra sol kenardaki \((r,1)\) başlangıçlarından \(r \ge 2\) olacak biçimde başlatır. Böylece her sabit-\(j-i\) köşegeni tam bir kez taranır.
Sol aşağı köşegenler ise \(i+j\) toplamıyla belirlenir. Bu yüzden başlangıç noktaları önce üst kenardaki \((1,c)\), sonra sağ kenardaki \((r,n)\) ve yine \(r \ge 2\) olacak şekilde seçilir. Böylece hiçbir köşegen atlanmaz ve hiçbiri iki kez başlanmaz.
Her iki köşegen ailesinin uzunluk dizisi
$$1,2,\dots,n-1,n,n-1,\dots,2,1$$
şeklindedir ve toplamı \(n^2\)'dir. Yani tek bir köşegen ailesi de toplamda tam bir satır taraması kadar hücre okur.
Diyelim ki bir satır ya da köşegen şu değerleri içeriyor:
$$L=(-8,3,5,-2,4,-10,6,7).$$
Her konumda biten en iyi toplamlar
$$B=(-8,3,8,6,10,0,6,13)$$
olur. Bu dizinin yorumu önemlidir. Altıncı değerde en iyi toplam \(-10\) değil \(10-10=0\)'dır; çünkü önceki iyi parçayı uzatmak yeni başlamaktan daha iyidir. Sekizinci değerde \(13\)'e ulaşılır, dolayısıyla bu doğru içindeki en iyi bitişik blok \(6+7=13\) eder.
Gerçek problemde yapılan şey, bu aynı hesabı \(2000 \times 2000\) tablodaki bütün satırlara, sütunlara ve köşegenlere uygulamaktır.
C++, Python ve Java uygulamaları önce \(4{,}000{,}001\) uzunluklu tek boyutlu bir dizi benzeri yapı ayırır; böylece gecikmeli dizi 1-indeksli tutulabilir. İlk 55 terim kübik formülle, kalan terimler ise 24 ve 55 gecikmeli bağıntıyla üretilir. Sıfır-indeksli döngülerde \((r,c)\) hücresi, satır-major yerleşimdeki \(rn+c+1\) konumundan okunur.
Üretim tamamlandıktan sonra dört ayrı geçiş yapılır: bütün satırlar, bütün sütunlar, bütün sağ aşağı köşegenler ve bütün sol aşağı köşegenler. Her yeni doğru başlamadan önce, o doğru için geçerli olan "burada biten en iyi toplam" çok negatif bir başlangıç değeriyle sıfırlanır; sonra her yeni hücre \(v\) için \( \max(v,\text{mevcut}+v) \) güncellemesi uygulanır.
Köşegenler için ayrıca geçici yardımcı diziler kurulmaz. Doğrular doğrudan sınır başlangıçlarından yürünür ve hücreler anında maksimum alt dizi bağıntısına beslenir.
Bir doğru taranırken aynı anda genel en iyi değer de güncellenir. Dört aile bittiğinde bu küresel değer tam cevaptır; çünkü izin verilen her bitişik parça bu taramalardan tam birinde görünmüştür.
Üç dildeki uygulama aynı matematiği ve aynı dolaşım sırasını kullanır; fark sadece sözdizimi ve veri yapılarıdır.
\(n=2000\) için dizi üretimi \(n^2\) adımdır. Satır taraması \(n^2\), sütun taraması bir \(n^2\) daha, iki köşegen ailesi de ayrı ayrı \(n^2\) hücre okur. Toplam iş miktarı
$$n^2+n^2+n^2+n^2+n^2=5n^2=20{,}000{,}000$$
temel güncellemedir; yani zaman karmaşıklığı \(O(n^2)\)'dir.
Verilen uygulamalarda bellek karmaşıklığı \(O(n^2)\)'dir; çünkü bütün tablo üretilen dizi içinde saklanır. Kadane bağıntısının kendisi yalnızca \(O(1)\) ek alan ister. Ayrıca her hücre en fazla \(499999\) ve her doğru uzunluğu en fazla \(2000\) olduğundan, herhangi bir doğru toplamı \(2000 \cdot 499999 < 10^9\) sınırının altında kalır; bu da derlenmiş sürümlerde sabit genişlikli tamsayı aritmetiğinin yeterli olduğunu açıklar.
Una tabla de \(2000 \times 2000\) se llena fila por fila con una sucesion pseudoaleatoria \(s_1,s_2,\dots,s_{4{,}000{,}000}\). Entre todas las filas, todas las columnas y las dos familias de diagonales, hay que encontrar el segmento contiguo cuya suma sea maxima.
La parte dificil no es generar la tabla, sino evitar una enumeracion ingenua de todos los segmentos posibles. La observacion clave es que cualquier subsecuencia valida vive por completo en una sola linea unidimensional, y cada una de esas lineas se resuelve de forma optima con la recurrencia clasica del problema de subarreglo maximo.
Sea \(n=2000\). Las implementaciones generan primero la sucesion retardada centrada, luego la reinterpretan como una matriz \(n \times n\), y finalmente repiten el mismo barrido unidimensional sobre todas las direcciones relevantes.
Para \(1 \le k \le 55\), los terminos vienen dados por
$$s_k=\left(100003-200003k+300007k^3 \bmod 10^6\right)-500000.$$
Para \(56 \le k \le n^2\), la recurrencia pasa a ser
$$s_k=\left(s_{k-24}+s_{k-55}+10^6 \bmod 10^6\right)-500000.$$
Despues del modulo \(10^6\), cada valor queda en el intervalo \([-500000,499999]\). La tabla se llena en orden por filas:
$$A_{i,j}=s_{(i-1)n+j}\qquad (1 \le i,j \le n).$$
Asi, el verdadero objeto matematico es la matriz \(A\), mientras que el generador explica por que existen exactamente \(4{,}000{,}000\) celdas y por que cada una puede localizarse con un indice lineal.
Toda subsecuencia admisible debe ser contigua dentro de una sola fila, una sola columna, una diagonal hacia abajo a la derecha o una diagonal hacia abajo a la izquierda. No puede doblarse ni saltar posiciones. Eso permite definir cuatro familias:
$$R_i=(A_{i,1},A_{i,2},\dots,A_{i,n}),\qquad 1 \le i \le n,$$
$$C_j=(A_{1,j},A_{2,j},\dots,A_{n,j}),\qquad 1 \le j \le n,$$
$$D_p=(A_{i,j}: j-i=p),\qquad -(n-1) \le p \le n-1,$$
$$E_q=(A_{i,j}: i+j=q),\qquad 2 \le q \le 2n.$$
Si \(M(L)\) denota la mayor suma de un bloque contiguo dentro de una linea \(L\), entonces la respuesta es
$$\max\bigl(\{M(R_i)\}\cup\{M(C_j)\}\cup\{M(D_p)\}\cup\{M(E_q)\}\bigr).$$
La geometria bidimensional del problema queda reducida, por tanto, a enumerar cada linea pertinente exactamente una vez; la optimizacion real es siempre unidimensional.
Tomemos una linea escaneada \(x_1,x_2,\dots,x_m\). Definimos \(B_t\) como la mayor suma de un segmento contiguo que debe terminar en la posicion \(t\). Entonces
$$B_1=x_1,\qquad B_t=\max(x_t,\;B_{t-1}+x_t)\quad (t \ge 2).$$
La razon es completa: un segmento optimo que termina en \(t\) solo puede empezar de nuevo en \(t\) o extender el mejor segmento que ya terminaba en \(t-1\). No existe una tercera opcion.
Si ademas escribimos
$$G_t=\max(G_{t-1},B_t),$$
entonces \(G_t\) es la mejor suma contigua vista en el prefijo \(x_1,\dots,x_t\). Al terminar la linea, \(G_m=M(L)\). Esa es precisamente la forma dinamica del algoritmo de Kadane y usa memoria adicional constante.
Las filas y las columnas son directas, pero las diagonales exigen elegir bien los puntos de inicio. Cada diagonal hacia abajo a la derecha queda determinada por la diferencia \(j-i\), asi que hay \(2n-1\) de ellas. La implementacion las inicia en el borde superior \((1,c)\) para todo \(c\), y luego en el borde izquierdo \((r,1)\) para \(r \ge 2\). De ese modo cada diagonal de diferencia constante aparece una sola vez.
Las diagonales hacia abajo a la izquierda quedan determinadas por la suma \(i+j\). Por eso la implementacion empieza en el borde superior \((1,c)\) para todo \(c\), y despues en el borde derecho \((r,n)\) para \(r \ge 2\). De nuevo no hay omisiones ni duplicados.
La distribucion de longitudes en cualquiera de las dos familias es
$$1,2,\dots,n-1,n,n-1,\dots,2,1,$$
y su suma es \(n^2\). En total, una familia diagonal completa toca exactamente el mismo numero de celdas que un barrido completo por filas o por columnas.
Supongamos que una fila o una diagonal contiene
$$L=(-8,3,5,-2,4,-10,6,7).$$
Las mejores sumas que terminan en cada posicion son
$$B=(-8,3,8,6,10,0,6,13).$$
Ese vector explica la recurrencia. En la sexta posicion, por ejemplo, es mejor prolongar el segmento anterior y obtener \(10-10=0\) que empezar un nuevo segmento en \(-10\). En la octava posicion se alcanza \(13\), de modo que el mejor bloque contiguo de esa linea es \(6+7=13\).
El problema completo no hace nada conceptualmente distinto: repite este mismo calculo sobre todas las filas, todas las columnas y todas las diagonales de la tabla \(2000 \times 2000\).
Las implementaciones en C++, Python y Java reservan primero un contenedor unidimensional de longitud \(4{,}000{,}001\), lo que permite almacenar la sucesion con indexacion desde 1. Los primeros 55 terminos salen de la formula cubica; el resto se obtiene con la recurrencia de retardos 24 y 55. Con bucles indexados desde 0, la celda \((r,c)\) se lee directamente desde la posicion \(rn+c+1\).
Una vez generados los datos, el codigo realiza cuatro barridos independientes: filas, columnas, diagonales hacia abajo a la derecha y diagonales hacia abajo a la izquierda. Antes de cada nueva linea, reinicia el mejor valor que debe terminar en la posicion actual a un centinela muy negativo, y luego aplica la actualizacion \( \max(v,\text{actual}+v) \) a medida que va leyendo cada valor \(v\).
Las diagonales no se copian a arreglos auxiliares. Se recorren directamente desde sus puntos de arranque en el borde, consumiendo cada celda en el mismo momento en que se actualiza la recurrencia del subarreglo maximo.
Mientras se procesa cada linea, tambien se actualiza un maximo global. Cuando terminan los cuatro barridos, ese valor global es exactamente la respuesta, porque cualquier subsecuencia contigua permitida ha aparecido en uno y solo uno de esos recorridos.
Las tres versiones comparten la misma matematica y el mismo orden de recorrido; lo unico que cambia es la sintaxis y la representacion concreta de los datos.
Con \(n=2000\), generar la sucesion cuesta \(n^2\) pasos. El barrido por filas examina \(n^2\) celdas, el barrido por columnas otras \(n^2\), y cada familia diagonal aporta tambien \(n^2\). Por tanto, el trabajo total es
$$n^2+n^2+n^2+n^2+n^2=5n^2=20{,}000{,}000$$
actualizaciones elementales, es decir, tiempo \(O(n^2)\).
El espacio es \(O(n^2)\) en estas implementaciones porque toda la tabla queda almacenada a traves de la sucesion generada. La recurrencia de Kadane en si usa solo \(O(1)\) memoria extra. Ademas, como cada entrada es menor que \(500000\) en valor absoluto y una linea tiene longitud a lo sumo \(2000\), cualquier suma de linea queda por debajo de \(2000 \cdot 499999 < 10^9\), lo cual justifica que la aritmetica entera de ancho fijo sea suficiente en las versiones compiladas.
题目先用一个伪随机序列 \(s_1,s_2,\dots,s_{4{,}000{,}000}\) 按行填满一个 \(2000 \times 2000\) 的表格，然后要求在所有行、所有列以及两类对角线中，找出和最大的连续片段。
真正困难的地方不是生成这些数，而是不能把所有可能的连续片段都暴力枚举一遍。关键观察是：任何合法候选都完全落在一条一维直线上，而每一条这样的直线都可以用同一个最大子数组递推在一次扫描中求解。
记 \(n=2000\)。实现的整体思路分成三层：先生成居中的滞后序列，再把它看成一个 \(n \times n\) 矩阵，最后对四类方向分别做一维最大连续和扫描。
当 \(1 \le k \le 55\) 时，序列由显式公式给出：
$$s_k=\left(100003-200003k+300007k^3 \bmod 10^6\right)-500000.$$
当 \(56 \le k \le n^2\) 时，改用递推：
$$s_k=\left(s_{k-24}+s_{k-55}+10^6 \bmod 10^6\right)-500000.$$
做完模 \(10^6\) 之后，每个值都落在 \([-500000,499999]\) 之间。然后按行优先顺序填表：
$$A_{i,j}=s_{(i-1)n+j}\qquad (1 \le i,j \le n).$$
因此问题的数学对象其实是矩阵 \(A\)，而伪随机生成器的作用是告诉我们：一共有恰好 \(4{,}000{,}000\) 个单元，而且每个单元都可以由一个线性下标直接定位。
题目允许的连续片段必须完整地位于一行、一列、一条右下对角线或者一条左下对角线上。它不能转弯，也不能跳过元素。所以我们把所有候选分成四类：
$$R_i=(A_{i,1},A_{i,2},\dots,A_{i,n}),\qquad 1 \le i \le n,$$
$$C_j=(A_{1,j},A_{2,j},\dots,A_{n,j}),\qquad 1 \le j \le n,$$
$$D_p=(A_{i,j}: j-i=p),\qquad -(n-1) \le p \le n-1,$$
$$E_q=(A_{i,j}: i+j=q),\qquad 2 \le q \le 2n.$$
若 \(M(L)\) 表示一条直线 \(L\) 内部所有连续块中的最大和，那么最终答案就是
$$\max\bigl(\{M(R_i)\}\cup\{M(C_j)\}\cup\{M(D_p)\}\cup\{M(E_q)\}\bigr).$$
也就是说，二维部分只负责“把所有该扫描的直线列出来且不重不漏”，真正的优化问题始终是一维的。
设某条被扫描的直线为 \(x_1,x_2,\dots,x_m\)。定义 \(B_t\) 为“必须以位置 \(t\) 结尾的连续片段的最大和”，则有
$$B_1=x_1,\qquad B_t=\max(x_t,\;B_{t-1}+x_t)\quad (t \ge 2).$$
这个递推没有遗漏任何情况。一个以 \(t\) 结尾的最优连续片段，要么从 \(t\) 自己重新开始，要么就是把“以 \(t-1\) 结尾的最优片段”继续向右延伸一格，不会有第三种结构。
再定义
$$G_t=\max(G_{t-1},B_t),$$
那么 \(G_t\) 就表示前缀 \(x_1,\dots,x_t\) 中已经出现过的最大连续和。整条直线扫完后，\(G_m=M(L)\)。这正是 Kadane 算法的动态规划写法，而且只需要常数级额外空间。
行和列的枚举很直接，对角线则需要更严谨的边界设计。右下方向对角线由差值 \(j-i\) 唯一确定，因此共有 \(2n-1\) 条。实现先从上边界的所有 \((1,c)\) 出发，再从左边界的 \((r,1)\) 且 \(r \ge 2\) 出发。这样每个固定 \(j-i\) 的对角线都有且只有一个起点。
左下方向对角线由和 \(i+j\) 唯一确定。对应地，实现先从上边界的所有 \((1,c)\) 出发，再从右边界的 \((r,n)\) 且 \(r \ge 2\) 出发。于是每个固定 \(i+j\) 的对角线同样被精确覆盖一次。
任一类对角线的长度分布都是
$$1,2,\dots,n-1,n,n-1,\dots,2,1,$$
其总和为 \(n^2\)。这说明一整类对角线在总访问次数上，恰好与一次完整的行扫描或列扫描等价。
假设某一行或者某一条对角线上出现了下面这一串值：
$$L=(-8,3,5,-2,4,-10,6,7).$$
那么“以当前位置结尾的最优连续和”依次是
$$B=(-8,3,8,6,10,0,6,13).$$
这组数正好展示了递推的含义。比如第六个位置不是单独取 \(-10\)，而是把前面的最优和 \(10\) 延长后得到 \(0\)，因为 \(0\) 比 \(-10\) 更优。到第八个位置时得到 \(13\)，所以这条直线上的最佳连续片段就是 \(6+7=13\)。
整道题做的事情，本质上就是把同样的更新规则重复应用到 \(2000 \times 2000\) 表中的每一行、每一列和每一条对角线上。
C++、Python 和 Java 实现都会先分配一个长度为 \(4{,}000{,}001\) 的一维容器，以便按 1 下标存储伪随机序列。前 55 项由显式三次公式计算，后续项由 \(24\) 和 \(55\) 两个滞后量的递推式给出。这样一来，在使用 0 下标循环时，矩阵位置 \((r,c)\) 可以直接从线性位置 \(rn+c+1\) 读出。
生成完成后，程序做四轮扫描：所有行、所有列、所有右下对角线、所有左下对角线。每开始一条新直线，就把“当前必须在这里结尾的最优和”重置为一个很小的负哨兵值；每读到一个新元素 \(v\)，就执行 \( \max(v,\text{current}+v) \) 这一步更新。
对角线不会额外复制成临时数组，而是从边界起点直接向内走，一边访问矩阵单元，一边即时更新最大连续和状态。
在扫描某条直线的同时，程序也不断更新一个全局最大值。等四类方向全部处理完以后，这个全局值就是最终答案，因为所有合法的连续片段都已经在且仅在某一次扫描中出现过。
三种语言版本使用完全相同的数学结构和遍历顺序，差别只在语法形式和具体容器类型。
取 \(n=2000\)。生成序列需要 \(n^2\) 次更新；行扫描访问 \(n^2\) 个元素；列扫描再访问 \(n^2\) 个元素；两类对角线分别各访问 \(n^2\) 个元素。因此总工作量是
$$n^2+n^2+n^2+n^2+n^2=5n^2=20{,}000{,}000$$
次基本更新，也就是 \(O(n^2)\) 时间。
空间复杂度在这些实现中是 \(O(n^2)\)，因为全部表格数据都被保存在生成出的序列里。Kadane 递推本身只需要 \(O(1)\) 的附加状态。另外，每个单元都不超过 \(499999\)，每条直线的长度最多 \(2000\)，所以任意一条直线的总和都满足 \(2000 \cdot 499999 < 10^9\)；这也是为什么编译型实现用固定宽度整数就足够了。
Таблица размера \(2000 \times 2000\) заполняется построчно псевдослучайной последовательностью \(s_1,s_2,\dots,s_{4{,}000{,}000}\). Среди всех строк, всех столбцов и двух семейств диагоналей нужно найти непрерывный фрагмент с максимально возможной суммой.
Трудность задачи не в генерации чисел, а в том, что наивный перебор всех непрерывных фрагментов был бы слишком дорогим. Ключевое наблюдение состоит в том, что любой допустимый фрагмент целиком лежит на одной одномерной линии, а значит каждая такая линия решается одной и той же рекуррентной схемой максимального подмассива.
Положим \(n=2000\). Реализации сначала строят центрированную лаговую последовательность, затем рассматривают ее как матрицу \(n \times n\), а после этого многократно применяют одномерный алгоритм максимальной непрерывной суммы.
Для \(1 \le k \le 55\) последовательность задается формулой
$$s_k=\left(100003-200003k+300007k^3 \bmod 10^6\right)-500000.$$
Для \(56 \le k \le n^2\) используется рекуррентное соотношение
$$s_k=\left(s_{k-24}+s_{k-55}+10^6 \bmod 10^6\right)-500000.$$
После взятия по модулю \(10^6\) каждое значение лежит в интервале \([-500000,499999]\). Затем таблица заполняется в порядке строк:
$$A_{i,j}=s_{(i-1)n+j}\qquad (1 \le i,j \le n).$$
Тем самым основным объектом становится матрица \(A\), а генератор дает нам точные \(4{,}000{,}000\) значений и простую линейную адресацию каждой клетки.
Любая допустимая подпоследовательность должна быть непрерывной внутри одной строки, одного столбца, диагонали вниз-вправо или диагонали вниз-влево. Она не может поворачивать и не может пропускать элементы. Поэтому вся задача разбивается на четыре семейства:
$$R_i=(A_{i,1},A_{i,2},\dots,A_{i,n}),\qquad 1 \le i \le n,$$
$$C_j=(A_{1,j},A_{2,j},\dots,A_{n,j}),\qquad 1 \le j \le n,$$
$$D_p=(A_{i,j}: j-i=p),\qquad -(n-1) \le p \le n-1,$$
$$E_q=(A_{i,j}: i+j=q),\qquad 2 \le q \le 2n.$$
Если \(M(L)\) обозначает максимальную сумму непрерывного блока внутри линии \(L\), то ответ равен
$$\max\bigl(\{M(R_i)\}\cup\{M(C_j)\}\cup\{M(D_p)\}\cup\{M(E_q)\}\bigr).$$
Иными словами, вся двумерная часть задачи сводится к правильному перечислению нужных линий без пропусков и повторов; сама оптимизация всегда остается одномерной.
Рассмотрим любую сканируемую линию \(x_1,x_2,\dots,x_m\). Пусть \(B_t\) означает максимальную сумму непрерывного отрезка, который обязан заканчиваться в позиции \(t\). Тогда
$$B_1=x_1,\qquad B_t=\max(x_t,\;B_{t-1}+x_t)\quad (t \ge 2).$$
Это точная рекурсия: оптимальный отрезок, заканчивающийся в \(t\), либо начинается заново в \(t\), либо продолжает лучший отрезок, который заканчивался в \(t-1\). Других вариантов нет.
Если дополнительно ввести
$$G_t=\max(G_{t-1},B_t),$$
то \(G_t\) будет лучшей непрерывной суммой на префиксе \(x_1,\dots,x_t\). После завершения линии получаем \(G_m=M(L)\). Это и есть алгоритм Кадане в форме динамического программирования с \(O(1)\) дополнительной памятью.
Строки и столбцы очевидны, а для диагоналей нужно аккуратно выбрать стартовые клетки. Каждая диагональ вниз-вправо определяется разностью \(j-i\), значит таких диагоналей \(2n-1\). Реализация запускает их из верхней границы \((1,c)\) для всех \(c\), а затем из левой границы \((r,1)\) для \(r \ge 2\). Поэтому каждая диагональ с фиксированной разностью \(j-i\) появляется ровно один раз.
Диагонали вниз-влево определяются суммой \(i+j\). Для них стартовые точки берутся сначала на верхней границе \((1,c)\), затем на правой границе \((r,n)\) при \(r \ge 2\). Это снова дает полное покрытие без повторов.
Длины диагоналей в любом из двух семейств образуют последовательность
$$1,2,\dots,n-1,n,n-1,\dots,2,1,$$
а ее сумма равна \(n^2\). Значит каждое диагональное семейство в сумме посещает столько же клеток, сколько полный проход по строкам или по столбцам.
Пусть одна строка или диагональ содержит значения
$$L=(-8,3,5,-2,4,-10,6,7).$$
Тогда лучшие суммы, обязанные заканчиваться в каждой позиции, равны
$$B=(-8,3,8,6,10,0,6,13).$$
Именно эта последовательность показывает смысл рекурсии. В шестой позиции выгоднее продолжить прежний оптимум и получить \(10-10=0\), чем начать новый отрезок со значения \(-10\). В восьмой позиции получается \(13\), значит лучший непрерывный блок на этой линии равен \(6+7=13\).
Полная задача делает то же самое на всех строках, столбцах и диагоналях таблицы \(2000 \times 2000\).
Реализации на C++, Python и Java сначала выделяют одномерный контейнер длины \(4{,}000{,}001\), чтобы удобно хранить последовательность с индексацией от 1. Первые 55 членов вычисляются по явной кубической формуле, а остальные строятся по рекурсии с лагами 24 и 55. После этого клетка \((r,c)\) в нулевой индексации циклов читается напрямую из позиции \(rn+c+1\).
Далее код выполняет четыре отдельных прохода: по всем строкам, по всем столбцам, по всем диагоналям вниз-вправо и по всем диагоналям вниз-влево. Перед каждой новой линией текущее значение "лучшей суммы, заканчивающейся здесь" сбрасывается в очень маленький отрицательный сторожевой элемент, а затем обновляется формулой \( \max(v,\text{current}+v) \) для каждого прочитанного значения \(v\).
Для диагоналей не создаются вспомогательные массивы. Линии обходятся прямо от граничных стартовых точек, и каждое значение сразу подается в обновление максимального подмассива.
Во время обработки каждой линии одновременно обновляется и глобальный максимум. После завершения всех четырех семейств именно он и является ответом, потому что любой допустимый непрерывный отрезок встретился ровно в одном из этих проходов.
Все три версии используют одинаковую математику и одинаковый порядок обхода; различаются только синтаксис и типы контейнеров.
При \(n=2000\) генерация последовательности стоит \(n^2\) шагов. Проход по строкам читает \(n^2\) элементов, проход по столбцам еще \(n^2\), и каждое диагональное семейство тоже дает по \(n^2\) элементов. Следовательно, общее число базовых обновлений равно
$$n^2+n^2+n^2+n^2+n^2=5n^2=20{,}000{,}000,$$
то есть время работы составляет \(O(n^2)\).
Память в данных реализациях равна \(O(n^2)\), потому что весь набор значений хранится в сгенерированной последовательности. Сама рекурсия Кадане требует только \(O(1)\) дополнительного состояния. Поскольку каждый элемент не превосходит \(499999\), а длина линии не больше \(2000\), любая линейная сумма ограничена сверху величиной \(2000 \cdot 499999 < 10^9\); поэтому в компилируемых версиях достаточно обычной целочисленной арифметики фиксированной ширины.
يتم ملء جدول بحجم \(2000 \times 2000\) صفا بعد صف باستخدام المتتالية شبه العشوائية \(s_1,s_2,\dots,s_{4{,}000{,}000}\). المطلوب هو إيجاد المقطع المتجاور ذي أكبر مجموع بين جميع الصفوف وجميع الأعمدة وكلا عائلتي الأقطار.
الصعوبة الحقيقية ليست في توليد الأعداد، بل في أن تعداد جميع المقاطع المتجاورة بطريقة ساذجة سيكون مكلفا جدا. الفكرة الحاسمة هي أن كل مقطع مسموح به يقع بالكامل على خط واحد أحادي البعد، وأن كل خط من هذه الخطوط يمكن حله بأفضلية كاملة بواسطة نفس علاقة التكرار الخاصة بمشكلة الجزء الفرعي الأعظمي.
لنضع \(n=2000\). تقوم الحلول أولا بتوليد المتتالية المؤخرة والمتمركزة حول الصفر، ثم تعيد تفسيرها على أنها مصفوفة \(n \times n\)، وبعد ذلك تطبق المسح الأحادي البعد نفسه على جميع الاتجاهات المطلوبة.
من أجل \(1 \le k \le 55\) لدينا
$$s_k=\left(100003-200003k+300007k^3 \bmod 10^6\right)-500000.$$
ومن أجل \(56 \le k \le n^2\) تصبح العلاقة
$$s_k=\left(s_{k-24}+s_{k-55}+10^6 \bmod 10^6\right)-500000.$$
بعد الأخذ بترديد \(10^6\)، يبقى كل حد داخل المجال \([-500000,499999]\). ثم تملأ المصفوفة بترتيب الصفوف:
$$A_{i,j}=s_{(i-1)n+j}\qquad (1 \le i,j \le n).$$
إذن الكائن الرياضي الحقيقي في المسألة هو المصفوفة \(A\)، أما المولد فيوضح فقط أن لدينا بالضبط \(4{,}000{,}000\) قيمة وأن كل خلية يمكن الوصول إليها بفهرس خطي مباشر.
أي مقطع صالح يجب أن يكون متجاورا بالكامل داخل صف واحد أو عمود واحد أو قطر نازل إلى اليمين أو قطر نازل إلى اليسار. لا يسمح له بأن ينعطف أو يتجاوز عناصر. لذلك نقسم المسألة إلى أربع عائلات:
$$R_i=(A_{i,1},A_{i,2},\dots,A_{i,n}),\qquad 1 \le i \le n,$$
$$C_j=(A_{1,j},A_{2,j},\dots,A_{n,j}),\qquad 1 \le j \le n,$$
$$D_p=(A_{i,j}: j-i=p),\qquad -(n-1) \le p \le n-1,$$
$$E_q=(A_{i,j}: i+j=q),\qquad 2 \le q \le 2n.$$
إذا رمزنا بـ \(M(L)\) إلى أكبر مجموع لمقطع متجاور داخل خط \(L\)، فإن الجواب النهائي هو
$$\max\bigl(\{M(R_i)\}\cup\{M(C_j)\}\cup\{M(D_p)\}\cup\{M(E_q)\}\bigr).$$
وهكذا يصبح الجزء الثنائي البعد من المسألة مجرد مسألة تنظيم هندسي: عد كل خط ذي صلة مرة واحدة فقط، ثم طبق عليه نفس التحسين الأحادي البعد.
لنأخذ أي خط ممسوح \(x_1,x_2,\dots,x_m\). ولتكن \(B_t\) أكبر مجموع لمقطع متجاور يجب أن ينتهي عند الموضع \(t\). عندئذ
$$B_1=x_1,\qquad B_t=\max(x_t,\;B_{t-1}+x_t)\quad (t \ge 2).$$
هذه العلاقة كاملة تماما، لأن أفضل مقطع ينتهي عند \(t\) لا يملك إلا حالتين: إما أن يبدأ من جديد عند \(t\)، أو أن يمدد أفضل مقطع كان ينتهي عند \(t-1\). لا توجد بنية ثالثة ممكنة.
وإذا عرفنا كذلك
$$G_t=\max(G_{t-1},B_t),$$
فإن \(G_t\) يمثل أفضل مجموع متجاور ظهر داخل البادئة \(x_1,\dots,x_t\). وعند نهاية الخط نحصل على \(G_m=M(L)\). وهذا هو جوهر خوارزمية كادين بصياغة البرمجة الديناميكية مع ذاكرة إضافية ثابتة فقط.
الصفوف والأعمدة واضحة، أما الأقطار فتحتاج إلى اختيار دقيق لنقاط البداية. كل قطر نازل إلى اليمين يتحدد بالفرق \(j-i\)، ولذلك يوجد \(2n-1\) قطرا من هذا النوع. يبدأ التنفيذ هذه الأقطار من الحافة العليا \((1,c)\) لكل \(c\)، ثم من الحافة اليسرى \((r,1)\) عندما يكون \(r \ge 2\). بهذه الطريقة يظهر كل قطر ذي فرق ثابت مرة واحدة فقط.
أما الأقطار النازلة إلى اليسار فتتحدد بالمجموع \(i+j\). لذلك يبدأ التنفيذ من الحافة العليا \((1,c)\) لكل \(c\)، ثم من الحافة اليمنى \((r,n)\) عندما يكون \(r \ge 2\). وهكذا نحصل مرة أخرى على تغطية كاملة بلا تكرار.
أطوال الأقطار في أي من العائلتين تتبع النمط
$$1,2,\dots,n-1,n,n-1,\dots,2,1,$$
ومجموعها يساوي \(n^2\). أي أن عائلة قطرية كاملة تزور في المجموع العدد نفسه من الخلايا الذي تزوره عملية مسح كاملة للصفوف أو الأعمدة.
افترض أن أحد الصفوف أو الأقطار يحتوي القيم
$$L=(-8,3,5,-2,4,-10,6,7).$$
عندها تكون أفضل المجاميع التي يجب أن تنتهي في كل موضع هي
$$B=(-8,3,8,6,10,0,6,13).$$
هذه السلسلة تشرح معنى التكرار. عند الموضع السادس مثلا، من الأفضل تمديد المقطع السابق لنحصل على \(10-10=0\) بدلا من البدء من جديد بالقيمة \(-10\). وعند الموضع الثامن نصل إلى \(13\)، ولذلك فإن أفضل مقطع متجاور على هذا الخط هو \(6+7=13\).
المسألة الكاملة لا تفعل شيئا مختلفا من الناحية المفاهيمية؛ إنها تكرر التحديث نفسه على كل صف وكل عمود وكل قطر في جدول \(2000 \times 2000\).
تبدأ تطبيقات C++ وPython وJava بحجز بنية أحادية البعد طولها \(4{,}000{,}001\) حتى يمكن تخزين المتتالية بفهرسة تبدأ من 1. أول 55 حدا تأتي من الصيغة التكعيبية الصريحة، أما الحدود اللاحقة فتولد بعلاقة التأخيرين 24 و55. بعد ذلك يمكن قراءة الخلية \((r,c)\) مباشرة من الموضع \(rn+c+1\) عند استخدام حلقات ذات فهرسة صفرية.
بعد اكتمال التوليد، ينفذ البرنامج أربعة مسوح مستقلة: لجميع الصفوف، وجميع الأعمدة، وجميع الأقطار النازلة إلى اليمين، وجميع الأقطار النازلة إلى اليسار. قبل البدء بكل خط جديد، يعاد ضبط أفضل مجموع ينتهي عند الموضع الحالي إلى قيمة سالبة جدا، ثم تطبق خطوة التحديث \( \max(v,\text{current}+v) \) عند قراءة كل قيمة \(v\) جديدة.
لا تبنى مصفوفات مساعدة منفصلة للأقطار. بل يجري السير على كل قطر مباشرة من نقطة بدايته على الحافة، وتغذى كل خلية فورا في علاقة الجزء الفرعي الأعظمي.
أثناء مسح كل خط، يجري أيضا تحديث قيمة عظمى عالمية. وبعد انتهاء العائلات الأربع كلها، تكون هذه القيمة هي الجواب بالضبط، لأن كل مقطع متجاور مسموح به ظهر مرة واحدة فقط داخل أحد هذه المسوح.
الإصدارات الثلاثة تستخدم الرياضيات نفسها وترتيب المرور نفسه؛ والاختلاف بينها يقتصر على الصياغة وأنواع الحاويات.
عندما يكون \(n=2000\)، فإن توليد المتتالية يكلف \(n^2\) خطوة. ومسح الصفوف يزور \(n^2\) خلية، ومسح الأعمدة يزور \(n^2\) أخرى، وكل عائلة من عائلتي الأقطار تضيف أيضا \(n^2\) زيارة. لذلك يكون العمل الكلي
$$n^2+n^2+n^2+n^2+n^2=5n^2=20{,}000{,}000$$
تحديثا أساسيا، أي أن الزمن الكلي \(O(n^2)\).
التعقيد المكاني في هذه الحلول هو \(O(n^2)\)، لأنها تخزن الجدول كله عبر المتتالية المولدة. أما علاقة كادين نفسها فلا تحتاج إلا إلى \(O(1)\) من الحالة الإضافية. وبما أن كل عنصر أصغر من \(500000\) بالقيمة المطلقة وطول أي خط لا يتجاوز \(2000\)، فإن أي مجموع خطي يبقى دون \(2000 \cdot 499999 < 10^9\)، ولهذا تكفي الحسابات الصحيحة ذات العرض الثابت في النسخ المترجمة.