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

C++ में अधिकतम योग वाले k नॉन-ओवरलैपिंग सबलिस्ट्स का योग ढूंढने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और एक मान k है, हमें k नॉन-ओवरलैपिंग, नॉन-खाली सबलिस्ट्स ढूंढने हैं जैसे कि उनके योग का योग अधिकतम हो। हम मान सकते हैं कि k, nums के आकार से कम या बराबर है।

उदाहरण के लिए, यदि इनपुट है nums = [11, -1, 2, 1, 6, -24, 11, -9, 6] k = 3, तो आउटपुट 36 होगा, क्योंकि हम सबलिस्ट्स [11, -1, 2, 1, 6], [11], और [6] चुन सकते हैं जिससे योग [19, 11, 6] = 36 मिलता है।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम डायनामिक प्रोग्रामिंग का उपयोग करेंगे:

  1. n := nums का आकार
  2. यदि n == 0 या k == 0, तो 0 वापस करें
  3. आकार k+1 का एक ऐरे hi परिभाषित करें और -अनंत से भरें
  4. आकार k+1 का एक और ऐरे open परिभाषित करें और -अनंत से भरें
  5. hi[0] := 0
  6. nums में प्रत्येक num के लिए:
    • आकार k+1 का एक ऐरे nopen परिभाषित करें और -अनंत से भरें
    • i := 1 से k तक:
      • यदि open[i] > -अनंत, तो nopen[i] := open[i] + num
      • यदि hi[i-1] > -अनंत, तो nopen[i] := max(nopen[i], hi[i-1] + num)
    • open := move(nopen)
    • i := 1 से k तक: hi[i] := max(hi[i], open[i])
  7. hi[k] वापस करें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int>& nums, int k) {
    int n = nums.size();
    if (n == 0 || k == 0) return 0;
    vector<int> hi(k + 1, INT_MIN), open(k + 1, INT_MIN);
    hi[0] = 0;
    for (int num : nums) {
        vector<int> nopen(k + 1, INT_MIN);
        for (int i = 1; i <= k; ++i) {
            if (open[i] > INT_MIN)
                nopen[i] = open[i] + num;
            if (hi[i - 1] > INT_MIN)
                nopen[i] = max(nopen[i], hi[i - 1] + num);
        }
        open = move(nopen);
        for (int i = 1; i <= k; ++i)
            hi[i] = max(hi[i], open[i]);
    }
    return hi[k];
}

int main() {
    vector<int> v = {11, -1, 2, 1, 6, -24, 11, -9, 6};
    int k = 3;
    cout << solve(v, 3);
}

इनपुट

{11, -1, 2, 1, 6, -24, 11, -9, 6}, 3

आउटपुट

36
  1. C++ में बाइनरी ट्री में अधिकतम स्तर योग खोजें C++ में बाइनरी ट्री में अधिकतम स्तर योग खोजें

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें सकारात्मक और नकारात्मक मान हैं। हमारा कार्य बाइनरी ट्री में अधिकतम स्तर योग खोजना है। समस्या विवरण: हमारे पास एक बाइनरी ट्री है, हम बाइनरी ट्री में सभी स्तरों का योग खोजेंगे और फिर उनमें से अधिकतम लौटाएंगे।एक उदाहरण लेकर समस्या को समझते

  1. - पायथन में समान आकार की 3 नॉन-ओवरलैपिंग सबलिस्ट का सबसे बड़ा योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास nums नामक संख्याओं की एक लिस्ट है और एक मान k है, हमें दी गई लिस्ट के आकार k की तीन नॉन-ओवरलैपिंग सबलिस्ट का सबसे बड़ा योग ढूंढना है।उदाहरण के लिए, यदि इनपुट nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], k = 3 है, तो आउटपुट 27 होगा, क्योंकि हम सबलिस्ट [2, 2, 2], [4, 4, 4], और [3, 3

  1. - पायथन में दो नॉन-ओवरलैपिंग सबलिस्ट्स का अधिकतम योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और दो मान x और y हैं, हमें nums में दो नॉन-ओवरलैपिंग सबलिस्ट्स का अधिकतम योग ढूंढना है जिनकी लंबाई क्रमशः x और y है।उदाहरण के लिए, यदि इनपुट nums = [3, 2, 10, -2, 7, 6], x = 3, y = 1 है, तो आउटपुट 22 होगा, क्योंकि लंबाई 3 के लिए हम [3, 2, 10] चुनते ह