জাভাস্ক্রিপ্টে ডাইনামিক প্রোগ্রামিং দিয়ে পার্টিয়াল সম অ্যারে বের করা

সমস্যা বিবরণ

একটি অ্যারে দেওয়া আছে। প্রতিটি সাফিক্স (suffix) এর সমষ্টি বের করে একটি অ্যারে তৈরি করতে হবে।

ইনপুট: [1, 2, 3, 4, 5]

সাফিক্স সমষ্টি: [15, 14, 12, 9, 5, 0]

সমাধান (ডাইনামিক প্রোগ্রামিং)

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

const sumArray = (arr = []) => arr.reduce((a, b) => a + b, 0);

const partialSum = (arr = []) => {
  let sum = sumArray(arr);
  const res = [sum];
  for (let i = 0; i < arr.length; i++) {
    const el = arr[i];
    sum -= el;
    res.push(sum);
  }
  return res;
};

console.log(partialSum(arr)); // [15, 14, 12, 9, 5, 0]

আউটপুট

[ 15, 14, 12, 9, 5, 0 ]

ডাইনামিক প্রোগ্রামিং এডভান্টেজ

• টোটাল সমষ্টি একবার O(n) এ বের করা হয়।
• পরবর্তী সাফিক্স সমষ্টি O(1) এ বের করা হয় (পূর্বের সমষ্টি থেকে করেন্ট এলিমেন্ট বিয়োগ করে)।
• টোটাল টাইম O(n), স্পেস O(1) (রেজাল্ট অ্যারে বাদে)।