हमें किसी भी आकार के पूर्णांक तत्वों की एक सरणी दी गई है। कार्य अधिकतम योग का पता लगाना है जिसकी गणना दी गई सीमा के भीतर दिए गए सरणी से उप-सरणी बनाकर की जाएगी, जिसे किसी सरणी में किसी भी संभावित सूचकांक मान से शुरू किया जा सकता है।
आइए इसके लिए विभिन्न इनपुट आउटपुट परिदृश्य देखें -
में - 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 और कुल को अधिकतम मान के रूप में सेट करेगा।
-
सेट_नोड के रूप में संरचना की एक विधि बनाएं जो अधिकतम_वल को अधिकतम (बाएं। अधिकतम_वल, बाएं। कुल + दाएं। अधिकतम_वल), अधिकतम_टेम्प को अधिकतम (दाएं। अधिकतम_टेम्प, दाएं। कुल + बाएं। अधिकतम_टेम्प) के रूप में सेट करके पेड़ का निर्माण करेगी। लेफ्ट.टोटल + राइट.टोटल और सब_सम मैक्स के रूप में ({बाएं। सब_सम, राइट.सब_सम, लेफ्ट.मैक्स_टेम्प + राइट। मैक्स_वल}) फिर नोड लौटाएं।
-
बिल्ड_ट्री के रूप में एक विधि बनाएं जिसका उपयोग पेड़ बनाने के लिए किया जाएगा।
-
पहले IF की जाँच करें =अंतिम फिर कुल, max_temp, max_val और sub_sum को arr[first] के रूप में सेट करें और वापस लौटें।
-
बिल्ड_ट्री विधि को बिल्ड_ट्री (नोड, एआर, फर्स्ट, टेम्प, 2 * इनएक्स) और बिल्ड_ट्री (नोड, एआर, टेम्प + 1, लास्ट, 2 * इनएक्स + 1) के रूप में कॉल करें, फिर नोड [इनएक्स] को सेट_नोड्स पर सेट करें ( नोड [2 * inx], नोड [2 * inx + 1])
-
-
create_tree के रूप में एक विधि बनाएं और अस्थायी (int)(ceil(log2(size))) के रूप में सेट करें, फिर build_tree() विधि को पेड़, एआर, मान 0, सरणी के आकार के नोड ऑब्जेक्ट को पास करके कॉल करें -1, मान 1 तर्क के रूप में।
-
अधिकतम सबअरे योग को max_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx)
के रूप में खोजने के लिए एक विधि बनाएं।-
जांचें कि IF अस्थायी temp_4 से अधिक है या temp_2 temp_3 से कम है, तो NULL लौटाएं
-
जांचें कि IF अस्थायी temp_3 से अधिक है और temp_2 temp_4 से कम है, फिर नोड [inx]
लौटाएं -
फ़ंक्शन को कॉल करने के लिए बाईं ओर की विधि को कॉल करें max_sub (नोड, अस्थायी, मध्य, temp_3, temp_4, 2 * inx) और दाएँ से max_sub (नोड, मध्य + 1, temp_2, temp_3, temp_4, 2 * inx + 1 )
-
परिणाम को set_nodes (बाएं, दाएं) के रूप में सेट करें
-
वापसी परिणाम।
-
-
max_subarray(ट्री* नोड, इंट फर्स्ट, इंट लास्ट, इंट साइज) के रूप में एक विधि बनाएं
-
विधि के लिए एक कॉल बनाएं जैसे कि max_sub(node, 0, size-1, first, last, 1)
-
वापसी temp.sub_sum
-
-
मुख्य () फ़ंक्शन में
-
सकारात्मक और नकारात्मक मानों के साथ पूर्णांक प्रकारों की एक सरणी घोषित करें और एक सरणी के आकार की गणना करें।
-
पहली अनुक्रमणिका से अंतिम अनुक्रमणिका तक की सीमा निर्धारित करें।
-
दी गई श्रेणी में अधिकतम सबअरे योग की गणना करने के लिए फ़ंक्शन max_subarray(node, first, last, size) को कॉल करें
-
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define MAX 0x3f3f
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