بزرگ‌ترین زیرآرایه

ورودی یک آرایه از اعداد است، برای مثال arr = [1, -2, 3, 4, -9, 6].

کاری که باید انجام شود: زیرآرایه متوالی از arr را پیدا کنید که بیشترین مقدار جمع المان‌ها را دارد.

تابع getMaxSubSum(arr) را بنویسید که مقدار جمع را برگرداند.

برای مثال:

          getMaxSubSum([-1, 2, 3, -9]) == 5 (جمع المان‌های برجسته)
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 (همه را انتخاب می‌کنیم)
        

اگر تمام المان‌ها منفی باشند، به این معنی است که هیچ کدام را انتخاب نمی‌کنیم (زیرآرایه خالی است)، پس جمع برابر با صفر است:

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

لطفا سعی کنید یک راه حل سریع پیدا کنید: O(n²) یا حتی O(n) اگر می‌توانید.

باز کردن یک sandbox همراه با تست‌ها.

راه حل کُند

ما می‌توانیم تمام جمع‌های ممکن را حساب کنیم.

ساده‌ترین راه حل این است که تمام المان‌ها را دریافت کنیم و از آن المان به بعد، حاصل جمع تمامی زیرآرایه‌ها را حساب کنیم.

برای مثال، برای [11 ,9- ,3 ,2 ,1-]:

          // -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; // اگر هیچ المانی نگیریم، صفر برگردانده می‌شود

  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(n²) دارد، به عبارتی دیگر، اگر ما اندازه آرایه را دو برابر کنیم، الگوریتم 4 برابر بیشتر زمان می‌برد.

برای آرایه‌های بزرگ (1000، 10000 یا المان‌های بیشتر) چنین الگوریتمی می‌تواند باعث سستی جدی شود.

راه حل سریع

بیایید در آرایه پیش برویم و حاصل جمع کنونی المان‌ها را در متغیر s نگه داریم. اگر s در جایی منفی شود، سپس s=0 را مقداردهی می‌کنیم. بیشترین مقدار چنین sهایی جواب خواهد بود.

اگر توضیحات خیلی مبهم است، لطفا به کد نگاه کنید، به اندازه کافی کوتاه است:

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

  for (let item of arr) { // برای هر المان آرایه
    partialSum += item; // اضافه کن partialSum آن را به
    maxSum = Math.max(maxSum, partialSum); // بیشترین مقدار را یه یاد بسپر
    if (partialSum < 0) partialSum = 0; // اگر منفی بود برابر با منفی شود
  }

  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

الگوریتم دقیقا به 1 آرایه نیاز دارد، پس پیچیدگی زمان O(n) است.

شما می‌توانید اطلاعات بیشتری درباره الگوریتم را اینجا پیدا کنید: مسئله زیرآرایه بیشینه. اگر هنوز هم برای شما مشخص نیست که چرا کار می‌کند، لطفا الگوریتم را در مثال بالا دنبال کنید، ببینید چگونه کار می‌کند، این کار بهتر از حرفی است.

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

  for (let item of arr) {
    partialSum += item;
    maxSum = Math.max(maxSum, partialSum);
    if (partialSum < 0) partialSum = 0;
  }
  return maxSum;
}
        

باز کردن راه‌حل همراه با تست‌ها درون یک sandbox.