जावास्क्रिप्ट में उपसरणियों का सबसे बड़ा योग

समस्या

हमें एक जावास्क्रिप्ट फ़ंक्शन लिखना है जो गैर-ऋणात्मक पूर्णांकों की एक सरणी लेता है, एआर, पहले तर्क के रूप में और एक पूर्णांक, संख्या, (संख्या

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

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

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