C++ में सरणी विभाजन का सबसे बड़ा योग

मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी और एक मान m है। हम इस सरणी को m संख्या के सन्निकट उपसरणियों में विभाजित कर सकते हैं। हमें इन m उपसरणियों में सबसे बड़े योग को न्यूनतम करने के लिए एक एल्गोरिदम तैयार करना है।

तो यदि सरणी [7,2,4,10,9] है, और m = 2, तो योग 19 होगा, क्योंकि हम दो उपसरणियां बना सकते हैं जैसे [7,2,4] और [10,9], फिर सबसे बड़े योग वाली उपसरणी 19 है।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -

• एक फ़ंक्शन splitArray() परिभाषित करें, जो एक सरणी v, m लेगा,
• n := v का आकार
• आकार n की एक सरणी dp बनाएं
• आकार n की एक और सरणी sum बनाएं
• sum[0] := v[0]
• i := 1 से आरंभ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें -
  • sum[i] := sum[i - 1] + v[i]
• dp[0] := sum[n - 1]
• i := 1 से आरंभ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें -
  • dp[i] := sum[n - 1] - sum[i - 1]
• i := 1 से आरंभ करें, जब i < m, अपडेट करें (i को 1 से बढ़ाएं), करें -
  • start := 0 से आरंभ करें, जब start < n - i, अपडेट करें (start को 1 से बढ़ाएं), करें -
    • end := start + 1 से आरंभ करें, जब end <= n - i, अपडेट करें (end को 1 से बढ़ाएं), करें -
    • dp[start] := dp[start] और अधिकतम का न्यूनतम (start 0 है तो sum[end - 1], अन्यथा sum[end - 1] - sum[start - 1]) और dp[end]
• dp[0] लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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