मान लीजिए कि हमारे पास धनात्मक पूर्णांकों की एक सरणी है और एक मान m है। हम इस सरणी को m संख्या में सन्निहित उपसरणियों में विभाजित कर सकते हैं। हमें इन m उपसरणियों के बीच सबसे बड़े योग को कम करने के लिए एक एल्गोरिथम तैयार करना होगा।
इसलिए यदि सरणी [7,2,4,10,9], और m =2 कहें, तो योग 19 होगा, क्योंकि हम [7,2,4] और [10,9] जैसे दो उप-सरणी बना सकते हैं। , तो सबसे बड़ा योग वाला उप-सरणी 19 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक फ़ंक्शन स्प्लिटअरे () को परिभाषित करें, यह एक सरणी v, m, लेगा
- n :=v का आकार
- आकार की एक सरणी डीपी बनाएं
- आकार n का एक और सरणी योग बनाएं
- योग[0] :=v[0]
- इनिशियलाइज़ i :=1 के लिए, जब i
करें - योग[i] :=योग[i - 1] + v[i]
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int splitArray(vector<int>& v, int m) { int n = v.size(); vector <long long int > dp(n); vector <long long int> sum(n); sum[0] = v[0]; for(int i =1;i<n;i++)sum[i] =sum[i-1]+v[i]; dp[0] = sum[n-1]; for(int i =1;i<n;i++){ dp[i] = sum[n-1] - sum[i-1]; } for(int i =1;i<m;i++){ for(int start = 0;start<n-i;start++){ for(int end = start+1;end<=n-i;end++){ dp[start] = min(dp[start],max((start==0?sum[end-1]:sum[end-1]-sum[start-1]),dp[end])); } } } return dp[0]; } }; main(){ Solution ob; vector<int> v = {7,2,4,10,9}; cout << (ob.splitArray(v, 2)); }
इनपुट
[7,2,4,10,9] 2
आउटपुट
19