![]() |
Problema 149
Caută subșirul care are suma maximă
Privind la tabelul de mai jos, se poate verifica cu ușurință ca suma maximă posibilă a numerelor adiacente în orice direcție (pe orizontală, verticală, diagonală sau anti-diagonală) e 16 (= 8 + 7 + 1).
−2 | 5 | 3 | 2 |
9 | −6 | 5 | 1 |
3 | 2 | 7 | 3 |
−1 | 8 | −4 | 8 |
Să repetăm această căutare, dar pe o scară mult mai largă:
Pentru început, generează 4 milioane de numere pseudo-aleatorii folosind o anumită variantă a unui generator numit "Generator Fibonacci Întârziat":
Pentru 1 ≤ k ≤ 55, sk = [100003 − 200003k + 300007k3] (modulo 1000000) − 500000.
Pentru 56 ≤ k ≤ 4000000, sk = [sk−24 + sk−55 + 1000000] (modulo 1000000) − 500000.
Prin urmare, s10 = −393027 și s100 = 86613.
Termenii lui s sunt apoi aranjați într-un tabel de dimensiune 2000×2000, folosind primele 2000 de numere pentru a umple primul rând (secvențial), următoarele 2000 pentru a umple al doilea rând și așa mai departe.
Pentru final, găsește cea mai mare sumă de (oricâte) numere adiacente în orice direcție (pe orizontală, verticală, diagonală sau anti-diagonală).