Maksimal submassiv

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(n²) 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(n²). 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.