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

C++ में दी गई रेंज में अधिकतम उपसरणी योग

हमें किसी भी दिए गए आकार के पूर्णांक तत्वों की एक सरणी दी गई है। कार्य दिए गए रेंज के भीतर उपसरणी बनाकर गणना किए जाने वाले अधिकतम योग को ढूंढना है जो सरणी में किसी भी संभावित सूचकांक मान से शुरू हो सकता है।

विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं:

इनपुट: int arr[] = { 3, 2, -1, 6, 7, 2 }, int first = 0, int last = 5

आउटपुट: दी गई रेंज में अधिकतम उपसरणी योग: 19

व्याख्या: हमें एक सरणी दी गई है जिसमें धनात्मक और ऋणात्मक दोनों मान हैं और 0 से 5 तक की रेंज यानी सरणी के सभी सूचकांकों को कवर करती है। तो अधिकतम योग वाली उपसरणी 3 + 6 + 7 + 2 + 2 - 1 = 19 हो सकती है।

इनपुट: int arr[] = {-2, 1, 3, 4, 8, 9, 23}, int first = 0, int last = 3

आउटपुट: दी गई रेंज में अधिकतम उपसरणी योग: 8

व्याख्या: हमें एक सरणी दी गई है जिसमें धनात्मक और ऋणात्मक दोनों मान हैं और 0 से 3 तक की रेंज यानी सरणी के 0 से 3 सूचकांकों को कवर करती है। तो अधिकतम योग वाली उपसरणी 1 + 3 + 4 = 8 हो सकती है।

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण:

  • एक ट्री के लिए एक स्ट्रक्चर बनाएं जो max_val, max_temp, total, sub_sum को सदस्य वेरिएबल्स के रूप में संग्रहीत करेगा और डिफ़ॉल्ट कंस्ट्रक्टर का उपयोग करके max_val, max_temp, sum_sum और total को अधिकतम मानों के रूप में सेट करेगा।
  • स्ट्रक्चर की एक विधि set_node बनाएं जो max_val को max(left.max_val, left.total + right.max_val) के रूप में सेट करके ट्री बनाएगा, max_temp को max(right.max_temp, right.total + left.max_temp) के रूप में, total को left.total + right.total के रूप में और sub_sum को max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val}) के रूप में सेट करेगा फिर नोड लौटाएं।
  • ट्री बनाने के लिए build_tree विधि बनाएं।
    • जांचें यदि first == last तो total, max_temp, max_val और sub_sum को arr[first] पर सेट करें और लौटें।
    • build_tree विधि को build_tree(node, arr, first, temp, 2 * inx) और build_tree(node, arr, temp + 1, last, 2 * inx + 1) के रूप में कॉल करें फिर node[inx] को set_nodes(node[2 * inx], node[2 * inx + 1]) पर सेट करें।
  • create_tree विधि बनाएं और temp को (int)(ceil(log2(size))) पर सेट करें फिर build_tree() विधि को node ऑब्जेक्ट, arr, मान 0, सरणी का आकार -1, मान 1 को तर्क के रूप में पास करके कॉल करें।
  • अधिकतम उपसरणी योग ढूंढने के लिए maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx) विधि बनाएं।
    • जांचें यदि temp > temp_4 OR temp_2 < temp_3 तो NULL लौटाएं।
    • जांचें यदि temp >= temp_3 AND temp_2 <= temp_4 तो node[inx] लौटाएं।
    • left को फंक्शन maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx) और right को maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1) कॉल करने के लिए विधि कॉल करें।
    • result को set_nodes(left, right) पर सेट करें।
    • result लौटाएं।
  • maximum_subarray(Tree* node, int first, int last, int size) विधि बनाएं।
    • maximum_sub(node, 0, size - 1, first, last, 1) विधि को कॉल करें।
    • temp.sub_sum लौटाएं।
  • main() फंक्शन में:
    • धनात्मक और ऋणात्मक मानों के साथ पूर्णांक प्रकार की एक सरणी घोषित करें और सरणी का आकार गणना करें।
    • पहले सूचकांक से अंतिम सूचकांक तक रेंज परिभाषित करें।
    • दिए गए रेंज में अधिकतम उपसरणी योग की गणना करने के लिए फंक्शन maximum_subarray(node, first, last, size) कॉल करें।

उदाहरण

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

#define MAX 0x3f3f3f3f

struct Tree {
    int max_val;
    int max_temp;
    int total;
    int sub_sum;
    Tree() {
        max_val = max_temp = sub_sum = -MAX;
        total = -MAX;
    }
};

Tree set_nodes(Tree left, Tree right) {
    Tree node;
    node.max_val = max(left.max_val, left.total + right.max_val);
    node.max_temp = max(right.max_temp, right.total + left.max_temp);
    node.total = left.total + right.total;
    node.sub_sum = max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val});
    return node;
}

void build_tree(Tree* node, int arr[], int first, int last, int inx) {
    if (first == last) {
        node[inx].total = arr[first];
        node[inx].max_temp = arr[first];
        node[inx].max_val = arr[first];
        node[inx].sub_sum = arr[first];
        return;
    }
    int temp = (first + last) / 2;
    build_tree(node, arr, first, temp, 2 * inx);
    build_tree(node, arr, temp + 1, last, 2 * inx + 1);
    node[inx] = set_nodes(node[2 * inx], node[2 * inx + 1]);
}

Tree* create_tree(int arr[], int size) {
    int temp = (int)(ceil(log2(size)));
    int n = 2 * (int)pow(2, temp) - 1;
    Tree* node = new Tree[n];
    build_tree(node, arr, 0, size - 1, 1);
    return node;
}

Tree maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx) {
    if (temp > temp_4 || temp_2 < temp_3) {
        Tree nullNode;
        return nullNode;
    }
    if (temp >= temp_3 && temp_2 <= temp_4) {
        return node[inx];
    }
    int mid = (temp + temp_2) / 2;
    Tree left = maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx);
    Tree right = maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1);
    Tree result = set_nodes(left, right);
    return result;
}

int maximum_subarray(Tree* node, int first, int last, int size) {
    Tree temp = maximum_sub(node, 0, size - 1, first, last, 1);
    return temp.sub_sum;
}

int main() {
    int arr[] = { 3, 2, -1, 6, 7, 2 };
    int size = sizeof(arr) / sizeof(arr[0]);
    Tree* node = create_tree(arr, size);
    int first = 0;
    int last = 5;
    int sub_sum = maximum_subarray(node, first, last, size);
    cout << "Maximum Subarray Sum in a given Range is: " << sub_sum;
    return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:

Maximum Subarray Sum in a given Range is: 19
  1. - C++ में दिए गए रेंज के लिए अधिकतम प्रीफिक्स-सम

    समस्या कथनn पूर्णांकों का एक एरे और q क्वेरी दी गई हैं, प्रत्येक क्वेरी में l से r तक की एक रेंज होती है। रेंज l – r के लिए अधिकतम प्रीफिक्स-सम ढूंढें।उदाहरणयदि इनपुट एरे arr[] = {-1, 2, 3, -5} है और क्वेरी = 2 और रेंज हैं: l = 0, r = 3 l = 1, r = 3 तो आउटपुट 4 और 5 होगा।पहली क्वेरी में रेंज (

  1. - सख्ती से बढ़ते सब-अर्रे का अधिकतम योग खोजें C++ में

    मान लीजिए हमारे पास n पूर्णांकों का एक ऐरे है। सख्ती से बढ़ते सब-अर्रे का अधिकतम योग खोजें। तो यदि ऐरे [1, 2, 3, 2, 5, 1, 7] जैसा है, तो योग 8 होगा। इस ऐरे में तीन सख्ती से बढ़ते सब-अर्रे हैं ये हैं {1, 2, 3}, {2, 5} और {1, 7}। अधिकतम योग वाला सब-अर्रे {1, 7} है। इस समस्या को हल करने के लिए, हमें अध

  1. - C++ में डिवाइड एंड कंकर का उपयोग करके अधिकतम योग सबएरे

    मान लीजिए हमारे पास धनात्मक और ऋणात्मक मानों के साथ डेटा की एक सूची है। हमें सन्निहित सबएरे का योग ढूंढना है जिसका योग सबसे बड़ा है। मान लीजिए सूची में {-2, -5, 6, -2, -3, 1, 5, -6} है, तो अधिकतम सबएरे का योग 7 है। यह {6, -2, -3, 1, 5} का योग है।हम इस समस्या को डिवाइड एंड कंकर विधि का उपयोग करके हल