JavaScript में कदाने के एल्गोरिदम का उपयोग करके उपसरणी का अधिकतम योग ढूंढना

समस्या

हमें एक JavaScript फ़ंक्शन लिखना है जो पूर्णांकों (धनात्मक और ऋणात्मक दोनों) की एक सरणी, arr, को पहला और एकमात्र तर्क के रूप में लेता है।

हमारे फ़ंक्शन को रैखिक समय में किसी भी उपसरणी का अधिकतम योग वापस करना चाहिए।

किसी मनमाने इंडेक्स i पर local_maximum, arr[i] और arr[i] तथा इंडेक्स i-1 पर local_maximum के योग में से अधिकतम होता है।

यही हम एक सरणी के भीतर रैखिक समय में अधिकतम उपसरणी योग खोजने के लिए लागू करने जा रहे हैं।

उदाहरण के लिए, यदि फ़ंक्शन का इनपुट है -

इनपुट

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

आउटपुट

const output = 6;

आउटपुट व्याख्या

क्योंकि अधिकतम योग वाली उपसरणी है -

[4, -1, 2, 1]

उदाहरण

निम्नलिखित कोड है -

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSequence = (arr = []) => {
  let currentSum = 0;
  let maxSum = 0;
  for (let elem of arr) {
    const nextSum = currentSum + elem;
    maxSum = Math.max(maxSum, nextSum);
    currentSum = Math.max(nextSum, 0);
  }
  return maxSum;
};
console.log(maxSequence(arr));

आउटपुट

6