JavaScript में उप-सरणी का अधिकतम सन्निकट योग (Maximum Contiguous Subarray Sum)

हमें एक JavaScript फ़ंक्शन लिखना है जो धनात्मक और ऋणात्मक पूर्णांकों की एक सरणी लेता है। चूंकि सरणी में ऋणात्मक तत्व भी होते हैं, सन्निकट तत्वों का योग संभवतः ऋणात्मक या धनात्मक हो सकता है।

हमारा फ़ंक्शन सरणी से सन्निकट तत्वों की एक सरणी चुनना चाहिए जिसका योग सबसे अधिक हो। अंत में, फ़ंक्शन को वह सरणी वापस करनी चाहिए।

उदाहरण के लिए -

यदि इनपुट सरणी है -

const arr = [-2, -3, 4, -1, -2, 1, 5, -3];

तो अधिकतम संभव योग 7 है और आउटपुट उप-सरणी होनी चाहिए -

const output = [4, -1, -2, 1, 5];

उदाहरण

निम्नलिखित कोड देखें:

const arr = [-2, -3, 4, -1, -2, 1, 5, -3];

const maximumSubarray = (arr = []) => {
  let max = -Infinity;
  let currentSum = 0;
  let maxStartIndex = 0;
  let maxEndIndex = arr.length - 1;
  let currentStartIndex = 0;
  arr.forEach((currentNumber, currentIndex) => {
    currentSum += currentNumber;
    if (max < currentSum) {
      max = currentSum;
      maxStartIndex = currentStartIndex;
      maxEndIndex = currentIndex;
    }
    if (currentSum < 0) {
      currentSum = 0;
      currentStartIndex = currentIndex + 1;
    }
  });
  return arr.slice(maxStartIndex, maxEndIndex + 1);
};

console.log(maximumSubarray(arr));

आउटपुट

कंसोल पर निम्नलिखित आउटपुट प्राप्त होगा:

[ 4, -1, -2, 1, 5 ]