मान लीजिए, हमारे पास नंबर्स का ऐसा ऐरे है:
const arr = [1, 2, 3, 4, 5];
हर बार एक एलिमेंट कम लेते हुए, इस ऐरे को इस तरह अलग किया जा सकता है:
[1, 2, 3, 4, 5] [2, 3, 4, 5] [3, 4, 5] [4, 5] [5] []
हमें एक JavaScript फ़ंक्शन लिखना है जो ऐसा ऐरे लेता है। फ़ंक्शन को ऊपर वर्णित तरीके से ऐरे को अलग करना चाहिए।
फ़ंक्शन को फिर इन पार्ट्स के संबंधित योगों वाला एक ऐरे बनाना चाहिए और उस ऐरे को लौटाना चाहिए।
इसलिए, इस ऐरे के लिए आउटपुट इस तरह दिखना चाहिए:
const output = [15, 14, 12, 9, 5 0];
हम इस समस्या को हल करने के लिए डायनामिक प्रोग्रामिंग का उपयोग करेंगे। हम पहले पूरे ऐरे का योग O(n) समय में निकालेंगे, जो अंततः ऐरे का पहला एलिमेंट बन जाएगा। फिर दूसरी इटरेशन में, हम संबंधित एलिमेंट्स को घटाते रहेंगे ताकि आउटपुट ऐरे के एलिमेंट्स प्राप्त हो सकें। इस तरह हम इस समस्या को O(n) समय और O(1) स्पेस में हल कर सकते हैं।
उदाहरण
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 ]
