← 返回首页
Масиви
UK

Ми хочемо зробити цей проєкт з відкритим кодом доступним для людей у всьому світі.

Допоможіть перекласти цей підручник вашою мовою!

    КупитиEPUB/PDF
    Пошук
    Пошук
    Навчальна карта
    Світла темаТемна тема
    عربيDanskEnglishEspañolفارسیFrançaisIndonesiaItaliano日本語한국어РусскийTürkçeУкраїнськаOʻzbek简体中文
    1. Підручник
    2. Мова програмування JavaScript
    3. Типи даних
    6 вересня 2024 р.

    Масиви

    Об’єкти дозволяють зберігати набори значень з ключами. Це чудово.

    Але досить часто ми розуміємо, що нам необхідна впорядкована колекція даних, яка складається з 1-го, 2-го, 3-го тощо елементів. Наприклад, така колекція може знадобитись для зберігання списку користувачів, товарів, HTML елементів та ін.

    Використовувати об’єкти в такому випадку не зручно, тому що вони не надають методів управління порядком елементів. Ми не можемо вставити нову властивість “між” тих, що вже існують. Об’єкти просто не призначені для цього.

    Для зберігання впорядкованих колекцій існує інший тип даних, який має назву масив, Array.

    Оголошення

    Існує два типи синтаксису для створення порожнього масиву:

    let arr = new Array(); let arr = [];

    Майже завжди використовують другий тип синтаксису. Ми можемо вказати початкові елементи масиву у квадратних дужках:

    let fruits = ["Яблуко", "Апельсин", "Слива"];

    Елементи масиву нумеруються починаючи з нуля.

    Ми можемо отримати елемент масиву, вказавши його номер у квадратних дужках:

    let fruits = ["Яблуко", "Апельсин", "Слива"]; alert( fruits[0] ); // Яблуко alert( fruits[1] ); // Апельсин alert( fruits[2] ); // Слива

    Можемо замінити елемент:

    fruits[2] = 'Груша'; // тепер ["Яблуко", "Апельсин", "Груша"]

    …Або додати новий:

    fruits[3] = 'Лимон'; // тепер ["Яблуко", "Апельсин", "Груша", "Лимон"]

    Загальна кількість елементів масиву зберігається у його властивості length:

    let fruits = ["Яблуко", "Апельсин", "Слива"]; alert( fruits.length ); // 3

    Ми можемо переглянути масив цілком за допомогою alert

    let fruits = ["Яблуко", "Апельсин", "Слива"]; alert( fruits ); // Яблуко,Апельсин,Слива

    У масивах можуть зберігатись елементи будь-якого типу.

    Наприклад:

    // різні типи значень let arr = [ 'Яблуко', { name: 'Микола' }, true, function() { alert('привіт'); } ]; // отримати елемент з індексом 1 (об'єкт) та вивести його властивість name alert( arr[1].name ); // Микола // отримати елемент з індексом 3 (функція) та виконати її arr[3](); // привіт
    Кома в кінці

    Список елементів масиву, як і список елементів об’єкта може закінчуватись комою:

    let fruits = [ "Яблуко", "Апельсин", "Слива", ];

    Кома в кінці рядка спрощує процес додавання/видалення елементів, тому що всі рядки стають однотипними.

    Отримати останні елементи за допомогою “at”

    Нещодавнє доповнення
    Це нещодавнє доповнення до мови. У старих браузерах може бути потрібен поліфіл.

    Скажімо, нам потрібен останній елемент масиву.

    Деякі мови програмування дозволяють використовувати від’ємні індекси з цією ж метою, наприклад, fruits[-1].

    Проте в JavaScript це не працюватиме. Результат буде undefined, оскільки індекс у квадратних дужках трактується буквально.

    Ми можемо явно обчислити індекс останнього елемента, а потім отримати до нього доступ: fruits[fruits.length - 1].

    let fruits = ["Яблуко", "Апельсин", "Слива"]; alert( fruits[fruits.length-1] ); // Слива

    Трохи громіздко, чи не так? Нам потрібно двічі написати ім’я змінної.

    На щастя, є коротший синтаксис: fruits.at(-1):

    let fruits = ["Яблуко", "Апельсин", "Слива"]; // те саме, що й fruits[fruits.length-1] alert( fruits.at(-1) ); // Слива

    Інакше кажучи, arr.at(i):

    • те саме, що й arr[i], якщо i >= 0.
    • для від’ємних значень i він шукає елемент відступаючи від кінця масиву.

    Методи pop/push, shift/unshift

    Черга – один з найбільш популярних варіантів використання об’єкта. У комп’ютерних науках так позначають колекцію елементів, яка підтримує дві операції:

    • push додає елемент у кінець списку.
    • shift видаляє елемент на початку, зміщуючи чергу, таким чином, що 2-й елемент стає 1-м.

    Масиви підтримують обидві операції.

    На практиці це дуже часто стає у пригоді. Наприклад, черга з повідомлень, які необхідно показувати на екрані.

    Існує також інший варіант використання масивів – структура даних, яка називається стек.

    Вона підтримує два типи операцій:

    • push додає елементи в кінець.
    • pop видаляє елемент з кінця.

    Таким чином нові елементи завжди додаються або видаляються з “кінця”.

    Хорошим прикладом стеку є колода карт: нові карти кладуться на верх і беруться теж зверху:

    У стеках – останній доданий елемент повертається першим, цей принцип також називають LIFO (з англ. Last-In-First-Out, “останній прийшов – перший пішов”). Для черг ми використовуємо принцип FIFO (з англ. First-In-First-Out, “перший прийшов – перший пішов”).

    Масиви в JavaScript можуть працювати як стеки і як черги. Ми можемо додавати/видаляти елементи як на початку, так і у кінці масиву.

    В комп’ютерних науках структури даних, які дозволяють це робити, мають назву двобічна черга.

    Методи, які працюють з кінцем масиву:

    pop

    Видаляє останній елемент масиву та повертає його:

    let fruits = ["Яблуко", "Апельсин", "Груша"]; alert( fruits.pop() ); // видаляємо "Груша" та виводимо його alert( fruits ); // Яблуко,Апельсин

    Що fruits.pop(), що fruits.at(-1) – обидва повертають останній елемент масиву, але fruits.pop() також змінює масив, видаляючи його.

    push

    Додає елемент в кінець масиву:

    let fruits = ["Яблуко", "Апельсин"]; fruits.push("Груша"); alert( fruits ); // Яблуко,Апельсин,Груша

    Виклик fruits.push(...) рівнозначний fruits[fruits.length] = ....

    Методи, які працюють з початком масиву:

    shift

    Видаляє перший елемент з масиву та повертає його:

    let fruits = ["Яблуко", "Апельсин", "Груша"]; alert( fruits.shift() ); // видаляємо "Яблуко" та виводимо його alert( fruits ); // Апельсин,Груша
    unshift

    Додає елемент в початок масиву:

    let fruits = ["Апельсин", "Груша"]; fruits.unshift('Яблуко'); alert( fruits ); // Яблуко,Апельсин,Груша

    Методи push та unshift можуть додавати одразу декілька елементів:

    let fruits = ["Яблуко"]; fruits.push("Апельсин", "Персик"); // ["Яблуко", "Апельсин", "Персик"] fruits.unshift("Ананас", "Лимон"); // ["Ананас", "Лимон", "Яблуко", "Апельсин", "Персик"] alert( fruits );

    Внутрішня структура масивів

    Масив – це спеціальний вид об’єктів. Квадратні дужки використовують для доступу до властивості arr[0], що своєю чергою прийшло з синтаксису об’єктів. Це теж саме, що доступ до властивості об’єкта obj[key], де arr це об’єкт в якому числа використовуються як ключі.

    Масиви розширюють функціональність об’єкта тим, що надають можливість працювати з упорядкованими колекціями даних, а також надають доступ до властивості length. Але в основі це досі об’єкт.

    Запам’ятайте, JavaScript містить лише 8 базових типів даних (більше інформації у розділі Типи даних). Масив – це об’єкт, тому він поводить себе як об’єкт.

    Наприклад, копіюється за посиланням:

    let fruits = ["Банан"] let arr = fruits; // копіюється за посиланням (дві змінні посилаються на один масив) alert( arr === fruits ); // true arr.push("Груша"); // зміна масиву за посиланням alert( fruits ); // "Банан", "Груша" -- наразі два елементи

    …Але те, що робить масиви дійсно особливими –- це їх внутрішнє представлення. Рушій JavaScript намагається зберігати елементи масиву у неперервній області пам’яті, один за одним, як це представлено на ілюстраціях в цьому розділі, а також застосовує інші способи оптимізації, що дозволяють масивам працювати дуже швидко.

    Проте масиви втратять всю свою ефективність, якщо ми перестанемо працювати з ними як з “упорядкованою колекцією даних” і почнемо використовувати як звичайний об’єкт.

    Наприклад, технічно ми можемо виконати наступне:

    let fruits = []; // створюємо масив fruits[99999] = 5; // створюємо властивість, індекс якої набагато перевищує довжину масиву fruits.age = 25; // створюємо властивість з довільним ім'ям

    Це можливо тому, що в основі масивів – об’єкти. Ми можемо додати будь-які властивості до них.

    Але рушій зрозуміє, що ми використовуємо масиви, як звичайні об’єкти. Методи оптимізації, які використовуються для масивів в цьому випадку не підходять, тому вони будуть відключені та не принесуть ніякої користі.

    Варіанти неправильного використання масивів:

    • Додавання нечислових властивостей, таких як arr.test = 5.
    • Створення “дірок”, наприклад: arr[0], а за ним arr[1000] (та нічого між цими елементами).
    • Заповнення масиву у зворотному порядку, наприклад: arr[1000], arr[999] тощо.

    Будь ласка, думайте про масиви як про особливі структури для роботи з впорядкованими даними. Вони надають спеціальні методи для цього. Масиви дуже ретельно налаштовані на роботу з неперервними впорядкованими даними, тому використовуйте їх саме таким чином. Тому, якщо вам необхідні довільні ключі, дуже ймовірно, що вам більше підійдуть звичайні об’єкти {}.

    Продуктивність

    Методи push/pop працюють швидко, на відміну від методів shift/unshift, які працюють повільно.

    Чому працювати з кінцем масиву швидше, ніж з початком? Перегляньмо, що відбувається під час виконання:

    fruits.shift(); // видалити один елемент з початку

    Але недостатньо просто взяти та видалити елемент з номером 0. Всі інші елементи також необхідно пронумерувати ще раз.

    Операція shift має виконати 3 дії:

    1. Видалити елемент з індексом 0.
    2. Перемістити всі елементи вліво змінивши в них нумерацію – індекс 1 на 0, 2 на 1 і так далі.
    3. Оновити властивість length.

    Чим більше елементів у масиві, тим більше часу необхідно для того, щоб перемістити їх, більше операцій з пам’яттю.

    Теж саме відбувається з методом unshift: для того, щоб додати елемент в початок масиву, необхідно спочатку перемістити всі елементи масиву вправо збільшуючи їх індекси.

    А як щодо методів push/pop? Вони нічого не переміщують. Для видалення елементу з кінця масиву метод pop очищає індекс та скорочує властивість length.

    Дії при операції pop:

    fruits.pop(); // видаляємо один елемент з кінця масиву

    Метод pop не переміщує нічого, адже кожен елемент зберігає свій індекс. Саме тому цей метод так швидко працює.

    Метод push працює аналогічно.

    Цикли

    Один з найстаріших методів перебору елементів масиву – це цикл for по індексах:

    let arr = ["Яблуко", "Апельсин", "Груша"]; for (let i = 0; i < arr.length; i++) { alert( arr[i] ); }

    Але для масивів можливий інший варіант циклу, for..of:

    let fruits = ["Яблуко", "Апельсин", "Слива"]; // ітерується по елементах масиву for (let fruit of fruits) { alert( fruit ); }

    Цикл for..of не надає доступу до індексу поточного елементу, тільки до його значення, але у більшості випадків цього достатньо. До того ж це коротше.

    Технічно, оскільки масив це об’єкт, ми можемо використовувати цикл for..in:

    let arr = ["Яблуко", "Апельсин", "Груша"]; for (let key in arr) { alert( arr[key] ); // Яблуко, Апельсин, Груша }

    Але насправді це погана ідея. Існують потенційні проблеми:

    1. Цикл for..in ітерується по всіх властивостях, не тільки по числових.

      У браузерах та різних програмних середовищах існують масивоподібні об’єкти, які виглядають як масив. Тобто вони мають властивість length та індекси, проте вони також містять інші нечислові властивості та методи, які нам часто не потрібні. Цикл for..in відобразить і їх. Тому, коли нам необхідно працювати з масивами, ці “екстра” властивості можуть стати проблемою.

    2. Цикл for..in оптимізований для довільних об’єктів, не для масивів, і тому працює в 10-100 разів повільніше. Звісно, це все одно дуже швидко. Збільшення швидкості виконання має значення лише у вузьких місцях. Але ми все одно повинні бути обережні з відмінностями.

    Словом, не варто використовувати цикл for..in для масивів.

    Декілька слів про “length”

    Властивість length оновлюється автоматично, коли масив змінився. Якщо бути точнішим, то length відображає не кількість елементів в масиві, а індекс останнього елементу плюс один.

    Наприклад, один елемент з великим індексом дасть велику довжину:

    let fruits = []; fruits[123] = "Яблуко"; alert( fruits.length ); // 124

    Зверніть увагу, що зазвичай ми не використовуємо масив подібним чином.

    Інший цікавий момент стосовно властивості length – її можна перезаписати.

    Якщо ми вручну збільшимо length, нічого цікавого не відбудеться. Але якщо зменшимо, масив стане коротшим. Цей процес незворотній, наприклад:

    let arr = [1, 2, 3, 4, 5]; arr.length = 2; // скорочуємо до двох елементів alert( arr ); // [1, 2] arr.length = 5; // повертаємо попередню довжину ... alert( arr[3] ); // undefined: ..., а видалені значення не повертаються

    Отож, найпростіший метод очищення масиву це: arr.length = 0;.

    new Array()

    Існує ще один варіант створення масиву:

    let arr = new Array("Яблуко", "Груша", "etc");

    Він використовується рідше, адже використання квадратних дужок [] більш зручний спосіб. Крім того, new Array має певну особливість.

    Якщо new Array викликається з одним аргументом, а саме числом, він створить порожній масив з довжиною, яка дорівнює цьому числу.

    Подивімось, як можна завдати собі ведмежої послуги:

    let arr = new Array(2); // чи створиться масив [2] ? alert( arr[0] ); // undefined! елементи відсутні alert( arr.length ); // довжина 2

    Для того, щоб позбутись таких сюрпризів, ми використовуємо квадратні дужки [], якщо тільки ми дійсно не маємо причини для використання методу new Array.

    Багатовимірні масиви

    Масиви можуть містити елементи, які своєю чергою теж є масивами. Ми можемо використовувати це для створення багатовимірних масивів, наприклад, для зберігання матриць:

    let matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]; alert( matrix[1][1] ); // 5, центральний елемент

    toString

    Масиви по-своєму реалізують метод toString, який повертає список елементів розділених комою.

    Наприклад:

    let arr = [1, 2, 3]; alert( arr ); // 1,2,3 alert( String(arr) === '1,2,3' ); // true

    Спробуймо це:

    alert( [] + 1 ); // "1" alert( [1] + 1 ); // "11" alert( [1,2] + 1 ); // "1,21"

    Масиви не мають Symbol.toPrimitive, або робочого valueOf, вони реалізують лише метод toString таким чином, що [] стає порожнім рядком, [1] стає "1" або [1,2] стає "1,2".

    Коли бінарний оператор "+" додає щось до рядка, це конвертується в рядок та виглядає наступним чином:

    alert( "" + 1 ); // "1" alert( "1" + 1 ); // "11" alert( "1,2" + 1 ); // "1,21"

    Не порівнюйте масиви за допомогою ==

    На відміну від інших мов програмування, масиви в JavaScript не варто порівнювати за допомогою оператора ==.

    Цей оператор не має спеціальних методів для опрацювання масивів, тому він працює з ними, як з об’єктами.

    Згадаймо правила:

    • Два об’єкти рівні == лише коли вони посилаються на один об’єкт.
    • Якщо один з аргументів оператора == об’єкт, а інший – примітив, тоді об’єкт конвертується в примітив. Це пояснюється в розділі Перетворення об’єктів в примітиви.
    • …Лише два виключення – це null та undefined, які рівні == один одному та нічому більше.

    Строге порівняння === ще простіше, тому що не конвертує типи.

    Тому, якщо ми порівнюємо масиви оператором ==, то вони ніколи не будуть однаковими, за виключенням, коли ми порівнюємо дві змінні, які посилаються на один масив.

    Наприклад:

    alert( [] == [] ); // false alert( [0] == [0] ); // false

    Технічно ці масиви є різними об’єктами. Тому вони не рівні. Оператор == не порівнює елемент за елементом.

    Порівняння масиву з примітивами теж може дати досить цікаві результати:

    alert( 0 == [] ); // true alert('0' == [] ); // false

    В обох випадках ми порівнювали примітиви з масивом. Масив [] задля порівняння конвертується в примітив і стає порожнім рядком ''.

    Далі відбувається порівняння примітивів. Логіка такого порівняння описана в розділі Перетворення типу:

    // після того, як [] було конвертовано в '' alert( 0 == '' ); // true, тому що '' конвертується в число 0 alert('0' == '' ); // false, тут немає конвертації типів; це різні рядки

    Тож, як порівнювати масиви?

    Все просто: не використовуйте оператор ==. Натомість порівнюйте їх в циклі, елемент за елементом. Також можна використати методи перебору, про які написано в наступному розділі.

    Підсумки

    Масив – це особливий вид об’єкта, створений для зберігання та обробки впорядкованих елементів.

    Оголошення масиву:

    // квадратні дужки (як правило) let arr = [item1, item2...]; // new Array (набагато рідше) let arr = new Array(item1, item2...);

    Виклик new Array(number) створює масив з заданою довжиною, але без елементів.

    • Властивість length демонструє довжину масиву або, якщо точніше, останній цифровий індекс масиву плюс один. Це виконується автоматично методами масиву.
    • Якщо ми вручну скорочуємо length, масив зменшується (нагадаємо, що ця операція незворотна).

    Отримання елементів:

    • ми можемо отримати елемент за його індексом, ось так arr[0]
    • також ми можемо використати метод at(i), який допускає від’ємні індекси. Для від’ємних значень i він відступає від кінця масиву. Якщо i >= 0, він працює так само як arr[i].

    Ми можемо використовувати масив як двосторонню чергу за допомогою наступних операцій:

    • push(...items) додає items в кінець масиву.
    • pop() видаляє елемент з кінця масиву та повертає його.
    • shift() видаляє елемент з початку масиву та повертає його.
    • unshift(...items) додає items в початок масиву.

    Для того, щоб пройтись циклом по елементах масиву:

    • for (let i=0; i<arr.length; i++) – працює швидше, сумісний зі старими браузерами.
    • for (let item of arr) – новий синтаксис, лише для значень елементів (відсутній доступ до індексів масиву).
    • for (let i in arr) – ніколи не використовуйте!

    Для порівняння масивів, не використовуйте оператор == (так само як >, < та інші), тому що в них немає спеціальних методів для порівнювання масивів. Ці оператори працюють з масивами як з об’єктами, а це не те, що нам потрібно.

    Натомість для порівняння масивів використовуйте цикл for..of, щоб порівнювати елемент за елементом.

    Ми повернемось до масивів та вивчимо методи додавання, видалення, відокремлення елементів та сортування масивів в розділі Методи масивів.

    Завдання

    Чи скопійовано масив?

    важливість: 3

    Що продемонструє наступний код?

    let fruits = ["Apples", "Pear", "Orange"]; // додаємо нове значення в "копію" let shoppingCart = fruits; shoppingCart.push("Banana"); // Що в fruits? alert( fruits.length ); // ?
    рішення

    Відповідь 4:

    let fruits = ["Apples", "Pear", "Orange"]; let shoppingCart = fruits; shoppingCart.push("Banana"); alert( fruits.length ); // 4

    Це відбувається тому, що масиви — це об’єкти. Отже, shoppingCart та fruits посилаються на один і той самий об’єкт.

    Операції з масивами.

    важливість: 5

    Давайте спробуємо 5 операцій з масивом.

    1. Створіть масив styles з елементами “Jazz” та “Blues”.
    2. Додайте “Rock-n-Roll” в кінець масиву.
    3. Замініть значення в середині масиву на “Classics”. Ваш код для пошуку медіанного елемента має працювати для будь-яких масивів непарної довжини.
    4. Видаліть перший елемент масиву та покажіть його.
    5. Вставте Rap та Reggae на початок масиву.

    Вигляд масиву по ходу виконання операцій:

    Jazz, Blues Jazz, Blues, Rock-n-Roll Jazz, Classics, Rock-n-Roll Classics, Rock-n-Roll Rap, Reggae, Classics, Rock-n-Roll
    рішення
    let styles = ["Jazz", "Blues"]; styles.push("Rock-n-Roll"); styles[Math.floor((styles.length - 1) / 2)] = "Classics"; alert( styles.shift() ); styles.unshift("Rap", "Reggae");

    Виклик в контексті масиву

    важливість: 5

    Яким буде результат? Чому?

    let arr = ["a", "b"]; arr.push(function() { alert( this ); }); arr[2](); // ?
    рішення

    Виклик arr[2]() це – синтаксично старий-добрий obj[method](), в ролі obj ми маємо arr, а в ролі method ми маємо 2.

    Ми маємо виклик функції arr[2] як методу об’єкту. Відповідно, він отримає в якості this об’єкт arr та виведе масив:

    let arr = ["a", "b"]; arr.push(function() { alert( this ); }) arr[2](); // a,b,function(){...}

    Масив має 3 елемента, спочатку їх було 2, плюс функція.

    Сума введених чисел

    важливість: 4

    Напишіть функцію sumInput() яка:

    • Просить користувача ввести дані за допомогою prompt та зберігає їх в масив.
    • Закінчує робити запити в користувача після того, як введено не числове значення, порожня строка або натиснуто “відмінити”.
    • Підраховує та повертає суму елементів масиву.

    P.S. Нуль 0 це – валідне число, будь ласка, не зупиняйте функцію при введені 0.

    Запустити демонстрацію

    рішення

    Зверніть увагу на одну важливу річ у вирішенні цієї задачі. Ми не конвертуємо value в число одразу після prompt, тому що одразу після операції value = +value ми не зможемо відрізнити порожній рядок (зупинення роботи функції) від нуля (дійсне число). Тому ми робимо це пізніше.

    function sumInput() { let numbers = []; while (true) { let value = prompt("Введіть, будь ласка, номер", 0); // Обриваємо введення даних? if (value === "" || value === null || !isFinite(value)) break; numbers.push(+value); } let sum = 0; for (let number of numbers) { sum += number; } return sum; } alert( sumInput() );

    Максимальний підмасив

    важливість: 2

    На вході масив чисел, наприклад arr = [1, -2, 3, 4, -9, 6].

    Завдання: знайти неперервний підмасив arr з максимальною сумою елементів.

    Написати функцію getMaxSubSum(arr) яка повертає таку суму.

    Наприклад:

    getMaxSubSum([-1, 2, 3, -9]) == 5 (the sum of highlighted items) getMaxSubSum([2, -1, 2, 3, -9]) == 6 getMaxSubSum([-1, 2, 3, -9, 11]) == 11 getMaxSubSum([-2, -1, 1, 2]) == 3 getMaxSubSum([100, -9, 2, -3, 5]) == 100 getMaxSubSum([1, 2, 3]) == 6 (take all)

    Якщо всі елементи менші нуля, нічого не беремо, це означає, що підмасив пустий, а сума рівна нулю:

    getMaxSubSum([-1, -2, -3]) = 0

    Будь ласка, подумайте над швидким рішенням: O(n2) або навіть над рішенням O(n), якщо зможете.

    Відкрити пісочницю з тестами.

    рішення
    Повільне рішення

    Повільне рішення

    Ми можемо порахувати всі можливі підсуми.

    Найпростіший шлях – це порахувати суми всіх підмасивів, починаючи з кожного елемента.

    Наприклад, для [-1, 2, 3, -9, 11]:

    // Починаємо з -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

    Вирішення потребує використання циклів: зовнішний цикл проходить по елементах масиву, а внутрішній рахує підсуму починаючи з поточного елементу.

    function getMaxSubSum(arr) { let maxSum = 0; // якщо елементи відсутні - повертаємо 0 for (let i = 0; i < arr.length; i++) { let sumFixedStart = 0; for (let j = i; j < arr.length; j++) { sumFixedStart += arr[j]; maxSum = Math.max(maxSum, sumFixedStart); } } return maxSum; } alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5 alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11 alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3 alert( getMaxSubSum([1, 2, 3]) ); // 6 alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

    Таке рішення має оцінку часу виконання O(n2). Інакше кажучи, якщо ми збільшимо розмір масиву вдвічі, алгоритм буде виконуватися в 4 рази довше.

    Для великих масивів (1000, 10000 або більше елементів) подібні алгоритми можуть призводити до серйозних “пригальмувань” в роботі.

    Швидке рішення

    Швидке рішення

    Пройдемося по масиву і в процесі будемо накопичувати проміжну суму елементів в змінній s. Якщо в певний момент s стане меншою за 0, присвоїмо s=0. Максимальне значення з усіх s і буде відповіддю.

    Якщо пояснення не дуже зрозуміле, подивіться, будь ласка, на код – він досить лаконічний:

    function getMaxSubSum(arr) { let maxSum = 0; let partialSum = 0; for (let item of arr) { // for each item of arr partialSum += item; // add it to partialSum maxSum = Math.max(maxSum, partialSum); // remember the maximum if (partialSum < 0) partialSum = 0; // zero if negative } return maxSum; } alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5 alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11 alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3 alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100 alert( getMaxSubSum([1, 2, 3]) ); // 6 alert( getMaxSubSum([-1, -2, -3]) ); // 0

    Цей алгоритм потребує рівно один прохід по масиву, його оціночний час виконання – O(n).

    Ви можете дізнатися більше про цей алгоритм тут: Maximum subarray problem. Якщо досі не зрозуміло, як це працює, будь ласка, подивіться алгоритм у прикладах вище, це буде краще за будь-які слова.

    Відкрити рішення із тестами в пісочниці.

    Попередній урокНаступний урок
    Навчальна карта

    Коментарі

    прочитайте це, перш ніж коментувати…
    • Якщо у вас є пропозиції, щодо покращення підручника, будь ласка, створіть обговорення на GitHub або одразу створіть запит на злиття зі змінами.
    • Якщо ви не можете зрозуміти щось у статті, спробуйте покращити її, будь ласка.
    • Щоб вставити код, використовуйте тег <code>, для кількох рядків – обгорніть їх тегом <pre>, для понад 10 рядків – використовуйте пісочницю (plnkr, jsbin, codepen…)

    Глава

    Навігація по уроку

    Поділитися
    Редагувати на GitHub