- Notifications
You must be signed in to change notification settings - Fork184
Arrays#115
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Uh oh!
There was an error while loading.Please reload this page.
Arrays#115
Changes fromall commits
234e6ba1364709ccf80a60f5a84739fd6954d0ed20f3d5f49e63ed1cc4c0d100ec4f1a469f8b70c13849e144e4cf625bfdb29233618aa57d346df19553d1bf5c53bb034281770a33c749dda9482959f84f4a3cad3f3fd8dfbad78fe3b6dc337e4fecc934ebfeab4e7e3daeba3669527391552646b611f06946dc3File filter
Filter by extension
Conversations
Uh oh!
There was an error while loading.Please reload this page.
Jump to
Uh oh!
There was an error while loading.Please reload this page.
Diff view
Diff view
There are no files selected for viewing
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -1,43 +1,43 @@ | ||
| #Повільне рішення | ||
| Ми можемо порахувати всі можливі підсуми. | ||
| Найпростіший шлях - це порахувати суми всіх підмасивів, починаючи з кожного елемента. | ||
| Наприклад, для `[-1, 2, 3, -9, 11]`: | ||
| ```js no-beautify | ||
| //Починаємо з -1: | ||
| -1 | ||
| -1 + 2 | ||
| -1 + 2 + 3 | ||
| -1 + 2 + 3 + (-9) | ||
| -1 + 2 + 3 + (-9) + 11 | ||
| //Починаємо з 2: | ||
| 2 | ||
| 2 + 3 | ||
| 2 + 3 + (-9) | ||
| 2 + 3 + (-9) + 11 | ||
| //Починаємо з 3: | ||
| 3 | ||
| 3 + (-9) | ||
| 3 + (-9) + 11 | ||
| //Починаємо з -9 | ||
| -9 | ||
| -9 + 11 | ||
| //Починаємо з 11 | ||
| 11 | ||
| ``` | ||
| Вирішення потребує використання циклів: зовнішний цикл проходить по елементах масиву, а внутрішній рахує підсуму починаючи з поточного елементу. | ||
| ```js run | ||
| function getMaxSubSum(arr) { | ||
| let maxSum = 0; //якщо елементи відсутні - повертаємо 0 | ||
| for (let i = 0; i < arr.length; i++) { | ||
| let sumFixedStart = 0; | ||
| @@ -57,15 +57,15 @@ alert( getMaxSubSum([1, 2, 3]) ); // 6 | ||
| alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100 | ||
| ``` | ||
| Таке рішення має оцінку часу виконання[O(n<sup>2</sup>)](https://uk.wikipedia.org/wiki/Нотація_Ландау).Інакше кажучи, якщо ми збільшимо розмір масиву вдвічі, алгоритм буде виконуватися в 4рази довше. | ||
| Для великих масивів (1000, 10000або більше елементів) подібні алгоритми можуть призводити до серйозних "пригальмувань" роботі. | ||
| #Швидке рішення | ||
| Пройдемося по масиву і в процесі будемо накопичувати проміжну суму елементів в змінній`s`.Якщо в певний момент`s`стане меншою за 0, присвоїмо`s=0`.Максимальне значення з усіх`s`і буде відповіддю. | ||
| Якщо пояснення не дуже зрозуміле, подивіться, будь ласка, на код - він досить лаконічний: | ||
| ```js run demo | ||
| function getMaxSubSum(arr) { | ||
| @@ -89,6 +89,6 @@ alert( getMaxSubSum([1, 2, 3]) ); // 6 | ||
| alert( getMaxSubSum([-1, -2, -3]) ); // 0 | ||
Collaborator There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others.Learn more. Будь ласка, перекладіть також коментарі в коді вище. | ||
| ``` | ||
| Цей алгоритм потребує рівно один прохід по масиву, його оціночний час виконання - O(n). | ||
| Ви можете дізнатися більше про цей алгоритм тут: [Maximum subarray problem](http://en.wikipedia.org/wiki/Maximum_subarray_problem).Якщо досі не цілком зрозуміло, як це працює, будь ласка, подивіться алгоритм у прикладах вище, це буде краще за будь-які слова. | ||
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -2,15 +2,15 @@ importance: 2 | ||
| --- | ||
| #Максимальний підмасив | ||
| На вході масив чисел, наприклад `arr = [1, -2, 3, 4, -9, 6]`. | ||
| Завдання: знайти неперервний підмасив`arr`з максимальною сумою елементів. | ||
| Написати функцію`getMaxSubSum(arr)`яка повертає таку суму. | ||
| Наприклад: | ||
| ```js | ||
| getMaxSubSum([-1, *!*2, 3*/!*, -9]) == 5 (the sum of highlighted items) | ||
| @@ -21,10 +21,10 @@ getMaxSubSum([*!*100*/!*, -9, 2, -3, 5]) == 100 | ||
| getMaxSubSum([*!*1, 2, 3*/!*]) == 6 (take all) | ||
Collaborator There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others.Learn more. Будь ласка, перекладіть коментарі в коді вище. | ||
| ``` | ||
| Якщо всі елементи менші нуля, нічого не беремо, це означає, що підмасив пустий, а сума рівна нулю: | ||
| ```js | ||
| getMaxSubSum([-1, -2, -3]) = 0 | ||
| ``` | ||
| Будь ласка, подумайте над швидким рішенням: [O(n<sup>2</sup>)](https://uk.wikipedia.org/wiki/Нотація_Ландау) або навіть над рішеннямO(n), якщо зможете. | ||
Uh oh!
There was an error while loading.Please reload this page.