জাভাস্ক্রিপ্টে পার্টিশনের গড়ের সর্বোচ্চ যোগফল

সমস্যা

আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি সংখ্যার অ্যারে arr প্রথম আর্গুমেন্ট এবং একটি সংখ্যা num (যে num <= arr.length) দ্বিতীয় আর্গুমেন্ট হিসেবে নেবে।

ফাংশনটি অ্যারে arr-কে সর্বোচ্চ num টি সংলগ্ন (নন-ইম্পটি) গ্রুপে পার্টিশন করবে যাতে কোনো উপাদান বাদ না যায়।

সকল এরকম পার্টিশনের মাঝ থেকে ফাংশনটি সেটি বেছে নেবে যেখানে সব গ্রুপের গড়ের যোগফল সর্বোচ্চ।

এবং শেষে আমরা এই সর্বোচ্চ যোগফল ফেরত দেব।

উদাহরণস্বরূপ, যদি ইনপুট হয় –

ইনপুট

const arr = [10, 2, 3, 4, 10]; 
const num = 3;

আউটপুট

const output = 23;

আউটপুট ব্যাখ্যা

কারণ যদি অ্যারেটিকে এভাবে পার্টিশন করি –

[10], [2, 3, 4], [10]

তবে গড়ের যোগফল হবে –

10 + (9)/3 + 10 = 23

যা সকল পার্টিশনের মধ্যে সর্বোচ্চ।

উদাহরণ

নিচে কোডটি দেওয়া হল –

const arr = [10, 2, 3, 4, 10]; 
const num = 3; 
const greatestSum = (arr, num) => { 
  const sum = (arr = []) => arr.reduce((acc, num) => acc + num, 0); 
  let matrix = new Array(num + 1).fill(0).map(() => new Array(arr.length + 1).fill(0)); 
  for (let index = arr.length; index >= 0; index--) { 
    const current = new Array(num + 1).fill(0).map(() => new Array(arr.length + 1).fill(0)); 
    for (let currentK = num; currentK >= 0; currentK--) { 
      for (let count = arr.length - 1; count >= 0; count--) { 
        if (index === arr.length && currentK === num) { 
          current[currentK][count] = 0; 
        } else if (index < arr.length && currentK < num) { 
          current[currentK][count] = Math.max( 
            matrix[currentK][count + 1], 
            matrix[currentK + 1][0] + sum(arr.slice(index - count, index + 1)) / (count + 1) 
          ); 
        } else { 
          current[currentK][count] = -Infinity; 
        } 
      } 
    } 
    matrix = current; 
  } 
  return matrix[0][0]; 
}; 
console.log(greatestSum(arr, num));