জাভাস্ক্রিপ্টে ক্যাডেন-এর অ্যালগরিদম দিয়ে সর্বোচ্চ সাবঅ্যারে যোগফল

সমস্যা

আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি পূর্ণসংখ্যার অ্যারে arr (ধনাত্মক ও ঋণাত্মক উভয়) প্রথম ও একমাত্র আর্গুমেন্ট হিসেবে নেবে।

ফাংশনটি যেকোনো সাবঅ্যারের সর্বোচ্চ যোগফল লিনিয়ার টাইমে ফেরত দেবে।

একinske ঈশ্বরième সূচক i-তে local_maximum হল arr[i] এবং arr[i] + index 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));