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

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

برای مثال، برای [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.