জাভাস্ক্রিপ্টে সাবয়ারের বৃহত্তম যোগফল

সমস্যা

আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা অ-নেতিবাচক পূর্ণসংখ্যার একটি অ্যারে নেয়, প্রথম আর্গুমেন্ট হিসাবে arr এবং দ্বিতীয় আর্গুমেন্ট হিসাবে একটি পূর্ণসংখ্যা, num, (num

আমাদের ফাংশনের কাজ হল অ্যারেটিকে num-খালি অবিচ্ছিন্ন সাবয়ারেতে বিভক্ত করা। অ্যারেটিকে এমনভাবে বিভক্ত করা উচিত যাতে এটি এই সংখ্যার সাববারেগুলির মধ্যে বৃহত্তম যোগফলকে ছোট করে। আমাদের ফাংশনটি তখন সাবয়ারের মধ্যে জমে থাকা বৃহত্তম যোগফল ফেরত দেবে।

উদাহরণস্বরূপ, যদি ফাংশনে ইনপুট হয় −

const arr = [5, 1, 4, 8, 7];
const num = 2;

তারপর আউটপুট −

const output = 15;

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

যদিও মূল অ্যারেটিকে সাবয়ারেতে বিভক্ত করার চারটি উপায় রয়েছে কিন্তু আমরা যদি অ্যারেটিকে দুটি গ্রুপে বিভক্ত করি [5, 1, 4] এবং [8, 7] তাহলে এই দুটি গ্রুপের ক্ষুদ্রতম যোগফল হবে এবং এই দুটির মধ্যে বড়টি হবে 8 + 7 =15 যা আমাদের ফাংশনটি ফেরত দেওয়া উচিত।

উদাহরণ

এর জন্য কোড হবে −

const arr = [5, 1, 4, 8, 7];
const num = 2;
const splitArray = (arr = [], num = 1) => {
   let max = 0;
   let sum = 0;
   const split = (arr, mid) => {
      let part = 1;
      let tempSum = 0;
      for (let num of arr) {
         if (tempSum + num > mid) {
            tempSum = num;
            part++;
         } else {
            tempSum += num;
         }
      }
      return part;
   };
   for (let num of arr) {
      max = Math.max(max, num);
      sum += num;
   };
   let low = max;
   let high = sum;
   while (low < high) {
      let mid = Math.floor((high+low)/2);
      let part = split(arr, mid);
      if (part > num) {
         low = mid + 1;
      } else {
         high = mid;
      }
   }
   return low;
};
console.log(splitArray(arr, num));

কোড ব্যাখ্যা:

আমরা এখানে বাইনারি অনুসন্ধান ব্যবহার করেছি আমরা সেরা বিভাজন খুঁজে পেতে পারি কিনা তা পরীক্ষা করতে।

আউটপুট

কনসোলে আউটপুট হবে −

15