सी++ में स्प्लिट ऐरे सबसे बड़ा योग

मान लीजिए कि हमारे पास धनात्मक पूर्णांकों की एक सरणी है और एक मान 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