- Notifications
You must be signed in to change notification settings - Fork179
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
234e6ba
1364709
ccf80a6
0f5a847
39fd695
4d0ed20
f3d5f49
e63ed1c
c4c0d10
0ec4f1a
469f8b7
0c13849
e144e4c
f625bfd
b292336
18aa57d
346df19
553d1bf
5c53bb0
3428177
0a33c74
9dda948
2959f84
f4a3cad
3f3fd8d
fbad78f
e3b6dc3
37e4fec
c934ebf
eab4e7e
3daeba3
6695273
9155264
6b611f0
6946dc3
File 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 | ||
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) | ||
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.