Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

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

मान लीजिए कि हमारे पास धनात्मक पूर्णांकों की एक सरणी है और एक मान 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]
  • dp[0] :=sum[n - 1]
  • इनिशियलाइज़ i :=1 के लिए, जब i करें
  • dp[i] :=sum[n - 1] - sum[i - 1]
  • इनिशियलाइज़ i :=1 के लिए, जब i करें
  • प्रारंभिक प्रारंभ के लिए:=0, प्रारंभ होने पर
  • इनिशियलाइज़ एंड के लिए:=स्टार्ट + 1, जब एंड <=n - i, अपडेट (1 से एंड बढ़ाएँ), करें -
  • dp[शुरू] :=न्यूनतम dp[शुरू] और अधिकतम (योग [अंत -1] जब प्रारंभ 0 है, अन्यथा योग [अंत -1] - योग [प्रारंभ -1]) और डीपी [अंत]
  • रिटर्न डीपी[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

    1. सी ++ एसटीएल में ऐरे योग

      सरणी एक रैखिक डेटा संरचना है जो समान डेटा प्रकार के तत्वों को निरंतर स्मृति स्थानों में संग्रहीत करती है। सरणी योग सरणी के सभी तत्वों का योग है। सी ++ प्रोग्रामिंग भाषा में कई विधियां हैं जिनके साथ आप सरणी योग पा सकते हैं। शास्त्रीय पद्धति सरणी के सभी तत्वों का योग खोजने की मूल विधि सरणी के तत्वो

    1. सी++ सम ऐरे पहेली

      सरणी एक डेटा संरचना है जो एक ही डेटा प्रकार के कई तत्वों को संग्रहीत करती है। यह मूल्यों के पूरे सेट को एक साथ स्टोर कर सकता है। लेकिन इसकी लंबाई पहले से तय करने की जरूरत है। इस योग सरणी पहेली में, हमें एक निश्चित आकार, मान लीजिए n की एक सरणी A1 दी गई है। इस पहेली को हल करने के लिए, हम S1 नामक एक स

    1. सी ++ में एक सम ऐरे पहेली?

      यहां हम सरणी से संबंधित एक दिलचस्प समस्या देखेंगे। n तत्वों के साथ एक सरणी है। हमें n तत्वों की एक और सरणी बनानी है। लेकिन दूसरी सरणी की i-वें स्थिति i-वें तत्व को छोड़कर पहले सरणी के सभी तत्वों का योग धारण करेगी। और एक बाधा यह है कि हम इस समस्या में घटाव ऑपरेटर का उपयोग नहीं कर सकते हैं। यदि हम घट