25 август 2025

Massivlar

Obyektlar qadriyatlar to’plamini saqlashga imkon beradi. Juda soz.

Ammo ko’pincha biz ro’yhatlangan to’plamga ehtiyoj sezamiz, bu yerda bizda 1 chi, 2 chi, 3 chi element va h.k. Masalan, biz biror narsaning ro’yxatini saqlashimiz kerak: foydalanuvchilar, tovarlar, HTML elementlari va boshqalar.

Bu erda obyektni ishlatish qulay emas, chunki u elementlarning tartibini boshqarish usullarini taqdim etmaydi. Mavjud bo’lganlar orasida “o’rtasiga” yangi xususiyat kiritolmaymiz. Obyektlar bunday foydalanish uchun mo’ljallanmagan.

Ro’yhatlangan to’plamlarni saqlash uchun Array nomli maxsus ma’lumotlar tuzilishi mavjud.

Deklaratsiya

Bo’sh massiv yaratish uchun ikkita sintaksis mavjud:

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

Deyarli har doim ikkinchi sintaksis ishlatiladi. Qavsda dastlabki elementlarni yetkazib berishimiz mumkin:

let fruits = ["Olma", "Apelsin", "Uzum"];

Massiv elementlari noldan boshlab raqamlangan.

Elementni to’rtburchak qavs ichida uning soniga ko’ra olishimiz mumkin:

let fruits = ["Olma", "Apelsin", "Uzum"];

alert( fruits[0] ); // Olma
alert( fruits[1] ); // Apelsin
alert( fruits[2] ); // Uzum

Biz elementni almashtirishimiz mumkin:

fruits[2] = 'Nok'; // now ["Olma", "Apelsin", "Nok"]

…Yoki massivga yangisini qo’shish:

fruits[3] = 'Limon'; // now ["Olma", "Apelsin", "Nok", "Limon"]

Massivdagi elementlarning umumiy soni uning uzunligi length dir:

let fruits = ["Olma", "Apelsin", "Uzum"];

alert( fruits.length ); // 3

Biz massivni to’liq ko’rsatish uchun alert dan ham foydalanishimiz mumkin.

let fruits = ["Olma", "Apelsin", "Uzum"];

alert( fruits ); // Olma,Apelsin,Uzum

Massiv har qanday turdagi elementlarni saqlashi mumkin.

Masalan:

// qiymatlar aralashmasi
let arr = [ 'Olma', { name: 'Oybek' }, true, function() { alert('salom'); } ];

// obyektni 1 chi indeksini oling va keyin uning nomini ko'rsating
alert( arr[1].name ); // Oybek

// funktsiyani 3 chi indeksini oling va uni ishga tushiring
arr[3](); // salom
Osilgan vergul

Massiv, xuddi obyekt singari, vergul bilan tugashi mumkin:

let fruits = [
  "Olma",
  "Apelsin",
  "Uzum",
];

“Osilgan vergul” uslubi elementlarni kiritishni/olib tashlashni osonlashtiradi, chunki barcha satrlar bir xil bo’ladi.

Usullar pop/push, shift/unshift

A navbat – bu massivning eng keng tarqalgan ishlatilishlaridan biri. Kompyuter fanida bu ikkita operatsiyani qo’llab-quvvatlaydigan elementlarning tartiblangan to’plamini anglatadi:

  • push elementni oxiriga qo’shib qo’yadi.
  • shift boshidagi element olib tashlanadi, shunday qilib, ikkinchi element birinchiga aylanadi.

Massivlar ikkala operatsiyani qo’llab-quvvatlaydi.

Amalda bu bizga ko’pincha kerak. Masalan, ekranda ko’rsatilishi kerak bo’lgan xabarlar navbati.

Massivlar uchun yana bir holat mavjud – stek deb nomlangan ma’lumotlar tuzilishi .

U ikkita operatsiyani qo’llab-quvvatlaydi:

  • push oxiriga element qo’shadi.
  • pop oxiridan element oladi.

Shunday qilib, yangi elementlar har doim “oxiridan” qo’shiladi yoki olinadi.

Stek odatda kartalar to’plami sifatida tasvirlanadi: yuqoriga yangi kartalar qo’shiladi yoki yuqoridan olinadi:

JavaScript-dagi massivlar navbat sifatida ham, stek sifatida ham ishlashi mumkin. Ular sizga elementlarni boshiga yoki oxiriga qo’shish/olib tashlash imkonini beradi.

Kompyuter fanida bunga imkon beradigan ma’lumotlar tuzilishi deque deb nomlanadi.

Massiv oxiri bilan ishlaydigan usullar:

pop

Massivning oxirgi elementini ajratib oladi va qaytaradi:

let fruits = ["Olma", "Apelsin", "Nok"];

alert( fruits.pop() ); // "Nok" ni olib tashlang va chiqaring

alert( fruits ); // Olma, Apelsin
push

Elementni massivning oxiriga qo’shadi:

let fruits = ["Olma", "Apelsin"];

fruits.push("Nok");

alert( fruits ); // Olma, Apelsin, Nok

fruits.push(...) chaqiruvifruits[fruits.length] = …` ga teng.

Massivning boshi bilan ishlaydigan usullar:

shift

Massivning birinchi elementini ajratib oladi va uni qaytaradi:

let fruits = ["Olma", "Apelsin", "Nok"];

alert( fruits.shift() ); // Olmani olib tashlaydi va qaytaradi

alert( fruits ); // Apelsin, Nok
unshift

Elementni massiv boshiga qo’shadi:

let fruits = ["Apelsin", "Nok"];

fruits.unshift('Olma');

alert( fruits ); // Olma, Apelsin, Nok

push va unshift usullari bir vaqtning o’zida bir nechta elementlarni qo’shishi mumkin:

let fruits = ["Olma"];

fruits.push("Apelsin", "Nok");
fruits.unshift("Ananas", "Limon");

// ["Ananas", "Limon", "Olma", "Apelsin", "Nok"]
alert( fruits );

Ichki massiv qurilma

Massiv – obyektlarning maxsus turdagi ko’rinishi. arr[0] xususiyatiga kirish uchun ishlatiladigan kvadrat qavslar asosan obj[key] kabi oddiy kalit kirish sintaksisidir, bu yerda obj rolida massiv va key sifatida raqamli indeks mavjud.

Ular ro’yhatlangan ma’lumotlar to’plamlari va length xususiyati bilan ishlash uchun maxsus usullarni taqdim etadigan obyektlarni kengaytiradi. Ammo aslida bu hali ham obyekt.

Esingizda bo’lsa, JavaScript-da faqat 7 ta asosiy tur mavjud. Massiv obyektdir va shu bilan obyekt kabi o’zini tutadi.

Masalan, u havola orqali ko’chiriladi:

let fruits = ["Banan"]

let arr = fruits; // havola orqali nusxalash (ikkita o'zgaruvchan bir massivga murojaat qiladi)

alert( arr === fruits ); // true

arr.push("Nok"); // havola yordamida massivni o'zgartiring

alert( fruits ); // Banan, Nok - 2 items now

…Ammo massivlarni chindan ham maxsus qiladigan narsa ularning ichki ko’rinishi. Interpretatorlar o’z elementlarini tutashgan xotira maydonida, xuddi shu bobdagi rasmlarda tasvirlanganidek, ketma-ket saqlashga harakat qiladi va massivlarni chindan ham tez ishlashini ta’minlash uchun boshqa optimallashtirishlar ham mavjud.

Ammo biz “ro’yhatlangan to’plam” singari massiv bilan ishlashni to’htatsak va u bilan odatdagi obyekt kabi ishlay boshlasak, ularning barchasi buziladi.

Masalan, texnik jihatdan biz buni qila olamiz:

let fruits = []; // massiv yaratish

fruits[99999] = 5; // indeks uzunligidan ancha kattaroq xususiyatni tayinlash

fruits.age = 25; // hohlagan nom bilan xususiyat yaratish

Bu mumkin, chunki massivlar aslida obyektlardir. Biz ularga har qanday xususiyatlarni qo’shishimiz mumkin.

Ammo interpretator biz oddiy obyekt kabi massiv bilan ishlayotganimizni ko’radi. Massivga xos optimallashtirish bunday holatlarga mos kelmaydi va o’chiriladi, ularning foydalari yo’qoladi.

Massivni noto’g’ri ishlatish usullari:

  • arr.test = 5 kabi raqamli bo’lmagan xususiyatni qo’shish.
  • Teshiklarni yaratish, masalan: arr[0] va keyin arr[1000] qo’shish (va ular orasida hech narsa yo’q).
  • Massivni teskari tartibda to’ldirish, masalan arr[1000], arr[999] va boshqalar.

Iltimos, ro’yhatlangan massivlar bilan ishlash uchun massivlarni maxsus tuzilmalar deb hisoblang. Buning uchun ular maxsus usullarni taqdim etishadi. Massivlar ketma ket ro’yhatlangan ma’lumotlar bilan ishlash uchun JavaScript interpretatorining ichida ehtiyotkorlik bilan sozlangan, iltimos ularni shu tarzda ishlating. Agar sizga kalitlangan xususiyatlar kerak bo’lsa, ehtimol siz odatdagi obyektni {} ishlatishiz kerak.

Samaradorlik

push/pop tez ishlaydi, shift/unshift esa sekin ishlaydi.

Nega massivning boshidan ko’ra uning oxiri bilan ishlash tezroq? Keling, ijro paytida nima bo’lishini ko’rib chiqaylik:

fruits.shift(); // boshidan 1 ta elementni oling

Elementni 0 raqami bilan olib tashlash yetarli emas. Boshqa elementlarning ham raqamlarini o’zgartirish kerak.

shift operatsiyasi uchta narsani bajarishi kerak:

  1. 0 indeksli elementni olib tashlash.
  2. Barcha elementlarni chapga siljitish, ularning raqamlarini 1 dan 0 ga, 2 dan 1 ga va hokazo.
  3. length xususiyatini yangilash.

Massivda qancha element bo’lsa, ularni siljitish uchun ko’proq vaqt, xotira ishlari ko’proq bo’ladi.

Shunga o’xshash narsa unshift bilan sodir bo’ladi: massiv boshiga element qo’shish uchun avval mavjud elementlarni indekslarini oshirib, o’ng tomonga siljitishi kerak.

Va push/pop nima? Ular hech narsani siljitishga hojat yo’q. Elementni oxiridan ajratib olish uchun pop usuli indeksni tozalaydi va length ni qisqartiradi.

pop operatsiyasi uchun harakatlar:

fruits.pop(); // oxiridan 1 ta elementni oling

pop usuli hech narsani siljitishni hojat yo’q, chunki boshqa elementlar o’z indekslarini saqlaydi. Shuning uchun u juda tezkor.

Shunga o’xshash narsa push usuli bilan.

Tsiklar

Elementlarni ro’yhatlashning eng qadimgi usullaridan biri bu for tsikli:

let arr = ["Olma", "Apelsin", "Nok"];

for (let i = 0; i < arr.length; i++) {
  alert( arr[i] );
}

Ammo massivlar uchun for..of tsiklning yana bir shakli mavjud:

let fruits = ["Olma", "Apelsin", "Uzum"];

// massiv elementlari ustida takrorlanadi
for (let fruit of fruits) {
  alert( fruit );
}

for..of joriy element raqamiga kirish huquqini bermaydi, faqat uning qiymatiga, lekin aksariyat hollarda bu yetarli. Va bu qisqaroq.

Texnik jihatdan, massivlar ob’ekt bo’lgani uchun for..in dan foydalanish ham mumkin:

let arr = ["Olma", "Apelsin", "Nok"];

for (let key in arr) {
  alert( arr[key] ); // Olma, Apelsin, Nok
}

Ammo bu aslida yomon fikr. U bilan bog’liq muammolar mavjud:

  1. For..in tsikli nafaqat raqamli xususiyatlarni, balki barcha xususiyatlarni takrorlaydi. Brauzerda va boshqa muhitda “massivga o’xshash” deb nomlangan ob’ektlar mavjud, ular massivlarga o’xshaydi. Ya’ni, ular length va indekslar xususiyatlariga ega, ammo ular boshqa raqamli bo’lmagan xususiyatlar va usullarga ham ega bo’lishi mumkin, ular odatda bizga kerak emas. for..in tsikl ularni ro’yxatlaydi. Agar biz massivga o’xshash narsalar bilan ishlashimiz kerak bo’lsa, unda bu “qo’shimcha” xususiyatlar muammoga aylanishi mumkin.

  2. for..in tsikli massivlar uchun emas, balki umumiy obyektlar uchun optimallashtirilgan va shuning uchun 10-100 marta sekinroq. Albatta, bu hali ham juda tez. Tezlashish faqat to’siqlarda muhim bo’lishi mumkin yoki ahamiyatsiz bo’lib tuyulishi mumkin. Ammo shunga qaramay, farqni bilishimiz kerak.

Odatda, biz for..in massivlar uchun ishlatmasligimiz kerak.

“Length” haqida so’z

Biz massivni o’zgartirganda length xususiyati avtomatik ravishda yangilanadi. Aniqroq aytganda, bu aslida massivdagi qiymatlar soni emas, balki eng katta sonli indeks va plyus bir.

Masalan, katta indeksli bitta element katta uzunlikni beradi:

let fruits = [];
fruits[123] = "Olma";

alert( fruits.length ); // 124

E’tibor bering, biz odatda bunday massivlardan foydalanmaymiz.

length xususiyati bilan bog’liq yana bir qiziq narsa shundaki, u tayinlanishi mumkin.

Agar uni qo’lda oshirsak, qiziq narsa bo’lmaydi. Ammo biz uni kamaytirsak, massiv qisqartiriladi. Jarayon qaytarib bo’lmaydigan, bu yerda misol:

let arr = [1, 2, 3, 4, 5];

arr.length = 2; // 2 ta elementgacha qisqartiring
alert( arr ); // [1, 2]

arr.length = 5; // uzunlikni qaytaring
alert( arr[3] ); // undefined: qiymatlar qayta qaytarilmaydi

Shunday qilib, massivni tozalashning eng oddiy usuli: arr.length = 0;.

new Array()

Massiv yaratish uchun yana bitta sintaksis mavjud:

let arr = new Array("Olma", "Nok", "va hokazo");

U kamdan-kam qo’llaniladi, chunki to’rtburchaklar [] qisqaroq. Bundan tashqari, bu bilan juda ayyor xususiyati mavjud.

Agar new Array raqamli bitta argument bilan chaqirilsa, u elementlarsiz, lekin berilgan uzunlikdagi massivni yaratadi.

Keling, qanday qilib ayanchli xizmatni taqdim etishni ko’rib chiqaylik:

let arr = new Array(2); // u [2] massiv yaratadimi?

alert( arr[0] ); // undefined! elementlar yo'q.

alert( arr.length ); // length 2

Yuqoridagi kodda new Array(raqam) barcha elementlari undefined.

Bunday kutilmagan hodisalardan qochish uchun, odatda nima qilayotganimizni bilmasak, to’rtburchak qavslardan foydalanamiz.

Ko’p o’lchovli massivlar

Massivlar massiv bo’lgan elementlarga ega bo’lishi mumkin. Matritsalarni saqlash uchun biz uni ko’p o’lchovli massivlar uchun ishlatishimiz mumkin:

let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

alert( matrix[1][1] ); // markaziy element

toString

Massivlar elementlarning vergul bilan ajratilgan ro’yxatini qaytaradigan toString usulini o’z ichiga oladi.

Masalan:

let arr = [1, 2, 3];

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

Bundan tashqari, buni sinab ko’raylik:

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

Massivlarda Symbol.toPrimitive, shuningdek, hatto valueOf yo’q, ular faqat toString konvertatsiyasini amalga oshiradilar, shuning uchun bu erda [] bo’sh satrga aylanadi, [1] "1" "va [1,2] "1,2" ga aylanadi.

Binar plyus "+" operatori massivga biror narsa qo’shganda, u matnga aylantiriladi, shuning uchun keyingi qadam quyidagicha ko’rinadi:

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

<<<<<<< HEAD

Xulosa

=======

Don’t compare arrays with ==

Arrays in JavaScript, unlike some other programming languages, shouldn’t be compared with operator ==.

This operator has no special treatment for arrays, it works with them as with any objects.

Let’s recall the rules:

  • Two objects are equal == only if they’re references to the same object.
  • If one of the arguments of == is an object, and the other one is a primitive, then the object gets converted to primitive, as explained in the chapter Obyektlarni ibtidoiylarga aylantirish.
  • …With an exception of null and undefined that equal == each other and nothing else.

The strict comparison === is even simpler, as it doesn’t convert types.

So, if we compare arrays with ==, they are never the same, unless we compare two variables that reference exactly the same array.

For example:

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

These arrays are technically different objects. So they aren’t equal. The == operator doesn’t do item-by-item comparison.

Comparison with primitives may give seemingly strange results as well:

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

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

Here, in both cases, we compare a primitive with an array object. So the array [] gets converted to primitive for the purpose of comparison and becomes an empty string ''.

Then the comparison process goes on with the primitives, as described in the chapter Turlarni o'zgartirish:

// after [] was converted to ''
alert( 0 == '' ); // true, as '' becomes converted to number 0

alert('0' == '' ); // false, no type conversion, different strings

So, how to compare arrays?

That’s simple: don’t use the == operator. Instead, compare them item-by-item in a loop or using iteration methods explained in the next chapter.

Summary

fb4fc33a2234445808100ddc9f5e4dcec8b3d24c

Array – ro’yhatlangan ma’lumotlar elementlarini saqlash va boshqarish uchun mos bo’lgan maxsus ob’ekt turi.

  • Deklaratsiya:

    // kvadrat qavslar (odatiy)
    let arr = [item1, item2...];
    
    // new Array (juda kam ishlatiladi)
    let arr = new Array(item1, item2...);

    new Arryay(raqam) berilgan uzunlikdagi, ammo elementlarsiz massivni yaratadi.

<<<<<<< HEAD

  • length xususiyati – bu massiv uzunligi yoki aniqrog’i, uning oxirgi son ko’rsatkichi plyus bir. U massiv usullari bilan avtomatik ravishda o’rnatiladi.
  • Agar length ni qo`lda qisqartirsak, massiv qisqartiriladi. =======
  • The length property is the array length or, to be precise, its last numeric index plus one. It is auto-adjusted by array methods.
  • If we shorten length manually, the array is truncated.

fb4fc33a2234445808100ddc9f5e4dcec8b3d24c

Biz quyidagi amallar bilan massivni ishlatishimiz mumkin:

<<<<<<< HEAD

  • push(...ma'lumot) oxiriga ma'lumot qo’shiladi.
  • pop() elementni oxiridan olib tashlaydi va qaytaradi.
  • shift() elementni boshidan olib tashlaydi va qaytaradi.
  • unshift(...ma'lumot) elementlarni boshiga qo’shadi. =======
  • push(...items) adds items to the end.
  • pop() removes the element from the end and returns it.
  • shift() removes the element from the beginning and returns it.
  • unshift(...items) adds items to the beginning.

fb4fc33a2234445808100ddc9f5e4dcec8b3d24c

Massiv elementlari bo’ylab yurish uchun:

  • for (let i=0; i<arr.length; i++) – eng tez ishlaydi, eski brauzerga mos keladi.
  • for (let items of arr) – faqat buyumlar(items) uchun zamonaviy sintaksis,
  • for (let i in arr) – hech qachon foydalanmang.

<<<<<<< HEAD Biz qatorlarga qaytamiz va Massiv usullari bobida elementlarni qo’shish, olib tashlash, ajratish va saralash uchun ko’proq usullarni o’rganamiz.

To compare arrays, don’t use the == operator (as well as >, < and others), as they have no special treatment for arrays. They handle them as any objects, and it’s not what we usually want.

Instead you can use for..of loop to compare arrays item-by-item.

fb4fc33a2234445808100ddc9f5e4dcec8b3d24c

We will continue with arrays and study more methods to add, remove, extract elements and sort arrays in the next chapter Massiv usullari.

Vazifalar

Ushbu kod nimani ko’rsatishi kerak?

let fruits = ["Olamalar", "Nok", "Apelsin"];

// yangi qiymatni "nusxaga" ga qo'shish
let shoppingCart = fruits;
shoppingCart.push("Banan");

// fruits ning ichida nma bor?
alert(fruits.length); // ?

Natija 4:

let fruits = ["Olmalar", "Nok", "Apelsin"];

let shoppingCart = fruits;

shoppingCart.push("Banan");

alert( fruits.length ); // 4

Buning sababi, massivlar obyektlardir. Shunday qilib, shoppingCart ham, fruits ham bir xil massivga murojaat qilishadi.

Keling, 5 ta massiv operatsiyasini sinab ko’raylik.

  1. “Jazz” va “Blues” elementlari bilan massivni yarating.
  2. “Rock-n-Roll” ni oxiriga qo’shing.
  3. O’rtadagi qiymatni “Classics” bilan almashtiring. O’rtacha qiymatni topish uchun sizning kodingiz uzunlikdagi har qanday massivlar uchun ishlashi kerak.
  4. Massivning birinchi qiymatini o’chirib tashang va uni ko’rsating.
  5. Massivga Rap va Reggae ni oldinda qo’shing.

Jarayondagi massiv:

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");

Natija qanday? Nima uchun?

let arr = ["a", "b"];

arr.push(function () {
  alert(this);
});

arr[2](); // ?

arr[2]() chaqiruvi sintaktik ravishda eski obj[method](), bizda objarr rolida va 2method rolida.

Shunday qilib, biz obyekt usuli sifatida arr[2] funktsiyasini chaqiramiz. Tabiiyki, u arr obyektiga murojaat qilib this ni oladi va massivni chiqaradi:

let arr = ["a", "b"];

arr.push(function () {
  alert(this);
});

arr[2](); // a,b,function(){...}

Massivda 3 ta qiymat mavjud: dastlab unda ikkita qiymat mavjud edi, funktsiya qiymati qo’shildi.

sumInput() funktsiyasini yozing:

  • Foydalanuvchidan prompt yordamida qiymatlarni so’raydi va qiymatlarni massivda saqlaydi.
  • Foydalanuvchi raqamli bo’lmagan qiymatni, bo’sh satrni kiritganda yoki “Cancel” tugmachasini bosganda so’rashni tugatadi.
  • Massiv elementlari yig’indisini hisoblab chiqadi va qaytaradi.

P.S. Nol 0 to’g’ri raqam, iltimos, nolda kiritishni to’xtatmang.

Namoyishni ishga tushirish

Iltimos, yechimning nozik, ammo muhim tafsilotlariga e’tibor bering. Biz value ni prompt dan so’ng darhol raqamga aylantirmaymiz, chunki value = +value dan keyin biz bo’sh satrni (to’xtash belgisi) noldan (amaldagi raqam) ajrata olmaymiz. Buni biz keyinroq qilamiz.

function sumInput() {
  let numbers = [];

  while (true) {
    let value = prompt("Iltimos, raqamni kiriting", 0);

    // bekor qilishimiz kerakmi?
    if (value === "" || value === null || !isFinite(value)) break;

    numbers.push(+value);
  }

  let sum = 0;
  for (let number of numbers) {
    sum += number;
  }
  return sum;
}

alert(sumInput());

Kirish raqamlar massivi, masalan. arr = [1, -2, 3, 4, -9, 6].

Vazifa quyidagicha: elementlarning maksimal yig’indisi bilan arr ning tutashgan submassivini toping.

Ushbu summani qaytaradigan getMaxSubSum(arr) funktsiyasini yozing.

Masalan:

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)

Agar barcha narsalar salbiy bo’lsa, demak biz hech narsani olmaymiz (submasssiv bo’sh), shuning uchun yig’indisi nolga teng:

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

Iltimos, tezkor echimni o’ylab ko’ring: O(n2) yoki hatto imkoningiz bo’lsa, O(n).

Sinovlar bilan sandbox-ni oching.

Sekin yechim

Biz barcha mumkin bo’lgan qismiy yig’indilarni hisoblashimiz mumkin.

Eng oddiy usul – har bir elementni olib, undan boshlanadigan barcha subarray’larning yig’indisini hisoblashdir.

Masalan, [-1, 2, 3, -9, 11] uchun:

// -1 dan boshlash:
-1 - 1 + 2 - 1 + 2 + 3 - 1 + 2 + 3 + -9 - 1 + 2 + 3 + -9 + 11;

// 2 dan boshlash:
2;
2 + 3;
2 + 3 + -9;
2 + 3 + -9 + 11;

// 3 dan boshlash:
3;
3 + -9;
3 +
  -9 +
  11 -
  // -9 dan boshlash
  9 -
  9 +
  11;

// 11 dan boshlash
11;

Kod aslida ichma-ich tsikl: tashqi tsikl array elementlari bo’ylab, ichki esa joriy elementdan boshlanadigan qismiy yig’indilarni hisoblaydi.

function getMaxSubSum(arr) {
  let maxSum = 0; // agar hech qanday element olmasak, nol qaytariladi

  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

Bu yechimning vaqt murakkabligi O(n2). Boshqacha qilib aytganda, agar array hajmini 2 marta oshirsak, algoritm 4 marta sekinroq ishlaydi.

Katta array’lar (1000, 10000 yoki undan ko’p elementlar) uchun bunday algoritmlar jiddiy sekinlikka olib kelishi mumkin.

Tez yechim

Array bo’ylab yuramiz va elementlarning joriy qismiy yig’indisini s o’zgaruvchida saqlaymiz. Agar s qandaydir nuqtada salbiy bo’lib qolsa, s=0 qilib belgilaymiz. Barcha bunday s larning maksimali javob bo’ladi.

Agar tavsif juda noaniq bo’lsa, kodni ko’ring, u yetarlicha qisqa:

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) {
    // arr ning har bir elementi uchun
    partialSum += item; // uni partialSum ga qo'sh
    maxSum = Math.max(maxSum, partialSum); // maksimalni eslab qol
    if (partialSum < 0) partialSum = 0; // agar salbiy bo'lsa nolga teng
  }

  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

Algoritm aynan 1 marta array’ni o’tishni talab qiladi, shuning uchun vaqt murakkabligi O(n).

Algoritm haqida batafsil ma’lumotni bu yerda topishingiz mumkin: Maximum subarray problem. Agar hali ham nima uchun ishlashi aniq bo’lmasa, yuqoridagi misollarda algoritmni kuzatib boring, qanday ishlashini ko’ring – bu har qanday so’zdan yaxshiroq.

Yechimni sandbox-dagi sinovlar bilan oching.

O'quv qo'llanma xaritasi

Izohlar

izoh berishdan oldin buni o'qing…
  • Agar sizda nimani yaxshilash kerakligi haqida takliflaringiz bo'lsa - iltimos, GitHub muammosini yuboring yoki izoh berish o'rniga so'rov yuboring.
  • Agar siz maqolada biror narsani tushunolmasangiz - iltimos, batafsilroq ma'lumot bering.
  • Bir nechta so'z so'zlarini kiritish uchun <code> yorlig'ini ishlating, bir nechta satrlar uchun - ularni <pre> yorlig'i bilan o'rab qo'ying, 10 satrdan ortiq bo'lsa - sandbox (plnkr, jsbin, codepen…)