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

C++ में 3 गैर-ओवरलैपिंग सबएरे का अधिकतम योग (Maximum Sum of 3 Non-Overlapping Subarrays)


मान लीजिए हमारे पास nums नामक एक ऐरे है जिसमें धनात्मक पूर्णांक हैं, हमें अधिकतम योग वाले तीन गैर-ओवरलैपिंग सबएरे ज्ञात करने हैं। यहां प्रत्येक सबएरे का आकार k होगा, और हम सभी 3*k प्रविष्टियों के योग को अधिकतम करना चाहते हैं।

हमें परिणाम को प्रत्येक अंतराल की प्रारंभिक स्थिति को दर्शाने वाले सूचकांकों की सूची के रूप में ज्ञात करना है। यदि कई उत्तर हैं, तो हम शब्दकोश क्रम में सबसे छोटा वाला वापस करेंगे।

तो यदि इनपुट [1,2,1,2,6,8,4,1] जैसा है और k = 2, तो परिणाम [0,3,5] होगा, तो सबएरे [1,2], [2,6], [8,4] हैं जो प्रारंभिक सूचकांक [0,3,5] से मेल खाते हैं।

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

  • n := nums का आकार
  • आकार 3 का एक ऐरे ret परिभाषित करें जिसे inf से भरें
  • आकार n + 1 का एक ऐरे sum परिभाषित करें
  • i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
    • sum[i + 1] = sum[i] + nums[i]
  • आकार n का एक ऐरे posLeft परिभाषित करें
  • आकार n का एक ऐरे posRight परिभाषित करें जिसे n - k से भरें
  • i := k से प्रारंभ करें, currMax := sum[k] - sum[0], जब i < n, i बढ़ाते हुए, करें -
    • newTotal := sum[i + 1] - sum[i + 1 - k]
    • यदि newTotal > currMax, तो -
      • currMax := newTotal
      • posLeft[i] := i + 1 - k
    • अन्यथा
      • posLeft[i] := posLeft[i - 1]
  • i := n - k - 1 से प्रारंभ करें, currMax := sum[n] - sum[n - k], जब i >= 0, i घटाते हुए, करें -
    • newTotal := sum[i + k] - sum[i]
    • यदि newTotal >= currMax, तो -
      • currMax := newTotal
      • posRight[i] := i
    • अन्यथा
      • posRight[i] := posRight[i + 1]
  • req := 0
  • i := k से प्रारंभ करें, जब i <= n - 2 * k, i बढ़ाते हुए, करें -
    • l := posLeft[i - 1], r := posRight[i + k]
    • temp := (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r])
    • यदि temp > req, तो -
      • ret[0] := l, ret[1] := i, ret[2] := r
      • req := temp
  • ret वापस करें

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

उदाहरण

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    cout << "]"<<endl; } class Solution { public:    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {       int n = nums.size();       vector <int> ret(3, INT_MAX);       vector <int> sum(n + 1);       for(int i = 0; i < n; i++){          sum[i + 1] = sum[i] + nums[i];       }       vector <int> posLeft(n);       vector <int> posRight(n, n - k);       for(int i = k, currMax = sum[k] - sum[0]; i < n; i++){          int newTotal = sum[i + 1] - sum[i + 1- k];          if(newTotal > currMax){             currMax = newTotal;             posLeft[i] = i + 1 - k;          }else{             posLeft[i] = posLeft[i - 1];          }       }       for(int i = n - k - 1, currMax = sum[n] - sum[n - k]; i >=0 ; i--){          int newTotal = sum[i + k] - sum[i];          if(newTotal >= currMax){             currMax = newTotal;             posRight[i] = i;          }else{             posRight[i] = posRight[i + 1];          }       }       int req = 0;       for(int i = k; i <= n - 2 * k; i++){          int l = posLeft[i - 1];          int r = posRight[i + k];          int temp = (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r]);          if(temp > req){             ret[0] = l;             ret[1] = i;             ret[2] = r;             req = temp;          }       }       return ret;    } }; main(){    Solution ob;    vector<int> v = {1,2,1,2,6,8,4,1};    print_vector(ob.maxSumOfThreeSubarrays(v, 2)); }

इनपुट

{1,2,1,2,6,8,4,1} 2

आउटपुट

[0, 3, 5, ]

  1. - C++ में मैट्रिक्स में अधिकतम पथ योग

    इस समस्या में, हमें M*N आकार का एक 2D मैट्रिक्स दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो मैट्रिक्स में अधिकतम पथ योग ढूंढेगा।यहां, मैट्रिक्स में अधिकतम पथ योग को एक पंक्ति से अंतिम पंक्ति तक सभी तत्वों के योग के रूप में परिभाषित किया गया है। पथ को पार करने के लिए अनुमत चालें नीचे की ओर और व

  1. - C++ में त्रिभुज में अधिकतम पथ योग

    इस समस्या में, हमें संख्याएँ त्रिभुज के रूप में दी गई हैं। हमारा कार्य एक प्रोग्राम बनाना है जो त्रिभुज में अधिकतम पथ योग ढूंढेगा। तत्वों को पहली पंक्ति से 1 तत्व के साथ व्यवस्थित किया जाता है और फिर अगली पंक्तियों में तत्वों की बढ़ती संख्या के साथ जब तक nवीं पंक्ति में तत्व नहीं होते। इसलिए, प्रोग

  1. - C++ में आकार K के M नॉन-ओवरलैपिंग सबएरे का अधिकतम योग

    समस्या कथन एक ऐरे और दो संख्याएं M और K दी गई हैं। हमें ऐरे में आकार K के अधिकतम M सबएरे का योग ढूंढना है (नॉन-ओवरलैपिंग)। (ऐरे का क्रम अपरिवर्तित रहता है)। K सबएरे का आकार है और M सबएरे की संख्या है। यह माना जा सकता है कि ऐरे का आकार m*k से अधिक है। यदि कुल ऐरे का आकार k का गुणक नहीं है, तो हम आंश