55 lines
2.4 KiB
Markdown
55 lines
2.4 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4021000cf542c50ff13
|
|||
|
|
title: 'Завдання 149. Пошук підпослідовності з максимальною сумою'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 301778
|
|||
|
|
dashedName: problem-149-searching-for-a-maximum-sum-subsequence
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Дивлячись на таблицю нижче, легко переконатися, що максимально можлива сума суміжних чисел у будь-якому напрямку (горизонтальному, вертикальному, діагональному чи антидіагональному) становить $16 (= 8 + 7 + 1)$.
|
|||
|
|
|
|||
|
|
$$\begin{array}{|r|r|r|r|} \hline −2 & 5 & 3 & 2 \\\\ \hline 9 & −6 & 5 & 1 \\\\ \hline 3 & 2 & 7 & 3 \\\\ \hline −1 & 8 & −4 & 8 \\\\ \hline \end{array}$$
|
|||
|
|
|
|||
|
|
Тепер повторимо пошук, але тільки в набагато більшому масштабі:
|
|||
|
|
|
|||
|
|
Спочатку, згенеруйте чотири мільйони псевдовипадкових чисел, використовуючи конкретну форму того, що відомо як "генератор Фібоначчі з запізненням":
|
|||
|
|
|
|||
|
|
Для $1 ≤ k ≤ 55$, $s_k = (100003 − 200003k + 300007{k}^3) \\ (modulo\\ 1000000) − 500000$.
|
|||
|
|
|
|||
|
|
Для $56 ≤ k ≤ 4000000$, $s_k = (s_{k − 24} + s_{k − 55} + 1000000) \\ (modulo\\ 1000000) − 500000$.
|
|||
|
|
|
|||
|
|
Таким чином, $s_{10} = −393027$ та $s_{100} = 86613$.
|
|||
|
|
|
|||
|
|
Потім члени $s$ розташовуються в таблиці 2000 × 2000, використовуючи перші 2000 чисел для заповнення першого рядка (послідовно), наступні 2000 чисел - для заповнення другого рядка і так далі.
|
|||
|
|
|
|||
|
|
В результаті знайдіть найбільшу суму (будь-якої кількості) суміжних записів в будь-якому напрямку (горизонтальному, вертикальному, діагональному або антидіагональному).
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`maximumSubSequence()` має повернути `52852124`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(maximumSubSequence(), 52852124);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function maximumSubSequence() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
maximumSubSequence();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|