আমরা যে কোনো আকারের পূর্ণসংখ্যা উপাদানগুলির একটি অ্যারে দিয়েছি। কাজটি হল সর্বাধিক যোগফল খুঁজে বের করা যা প্রদত্ত পরিসরের মধ্যে প্রদত্ত অ্যারে থেকে সাব্যারে গঠন করে গণনা করা হবে যা একটি অ্যারের যেকোনো সম্ভাব্য সূচক মান থেকে শুরু করা যেতে পারে।
আসুন এর জন্য বিভিন্ন ইনপুট আউটপুট পরিস্থিতি দেখি -
এ − 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 এবং মোট মান সর্বোচ্চ হিসাবে সেট করবে।
-
সেট_নোড হিসাবে কাঠামোর একটি পদ্ধতি তৈরি করুন যা max_val কে max(left.max_val, left.total + right.max_val), max_temp কে max(right.max_temp, right.total + left.max_temp), মোট হিসাবে সেট করে ট্রি গঠন করবে left.total + right.total এবং sub_sum হিসেবে max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val}) তারপর নোড ফেরত দিন।
-
বিল্ড_ট্রি হিসাবে একটি পদ্ধতি তৈরি করুন যা একটি গাছ তৈরি করতে ব্যবহার করা হবে।
-
প্রথমে IF চেক করুন =শেষ তারপর মোট সেট করুন, max_temp, max_val এবং sub_sum asr[first] এবং রিটার্ন করুন।
-
বিল্ড_ট্রি পদ্ধতিতে একটি কল করুন বিল্ড_ট্রি(নোড, অ্যাআর, ফার্স্ট, টেম্প, 2 * ইনক্স) এবং বিল্ড_ট্রি (নোড, অ্যাআর, টেম্প + 1, লাস্ট, 2 * ইনক্স + 1) তারপরে নোড[ইনক্স] সেট_নোডসে সেট করুন নোড[2 * inx], node[2 * inx + 1])
-
-
create_tree হিসাবে একটি পদ্ধতি তৈরি করুন এবং temp (int)(ceil(log2(size))) হিসাবে সেট করুন তারপর ট্রি, arr, মান 0, একটি অ্যারের আকার -1 এর নোড অবজেক্ট পাস করে build_tree() পদ্ধতিতে একটি কল করুন, একটি যুক্তি হিসাবে মান 1।
-
সর্বাধিক_সাব (ট্রি* নোড, int temp, int temp_2, int temp_3, int temp_4, int inx) হিসাবে সর্বাধিক সাবয়ারের যোগফল খুঁজে পেতে একটি পদ্ধতি তৈরি করুন
-
টেম্প_4-এর চেয়ে বেশি বা temp_2 temp_3-এর চেয়ে কম হলে চেক করুন তারপর NULL ফেরত দিন
-
temp_3-এর থেকে বেশি এবং temp_2 temp_4-এর চেয়ে কম হলে চেক করুন তারপর নোড [inx]
রিটার্ন করুন -
ফাংশন Max_sub(node, temp, mid, temp_3, temp_4, 2 * inx) এবং ডান থেকে Max_sub(নোড, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1) ফাংশনটি কল করতে বাম পদ্ধতিতে একটি কল করুন )
-
ফলাফল সেট_নোড (বাম, ডান)
হিসাবে সেট করুন -
ফলাফল ফেরত।
-
-
সর্বাধিক_সুবারে হিসাবে একটি পদ্ধতি তৈরি করুন (ট্রি* নোড, প্রথম int, int শেষ, int আকার)
-
সর্বাধিক_সাব (নোড, 0, আকার - 1, প্রথম, শেষ, 1) হিসাবে পদ্ধতিতে একটি কল তৈরি করুন
-
temp.sub_sum
ফেরত দিন
-
-
প্রধান() ফাংশনে
-
ধনাত্মক এবং ঋণাত্মক মান সহ পূর্ণসংখ্যা প্রকারের একটি অ্যারে ঘোষণা করুন এবং একটি অ্যারের আকার গণনা করুন৷
-
প্রথম সূচক থেকে শেষ সূচক পর্যন্ত পরিসর সংজ্ঞায়িত করুন।
-
প্রদত্ত পরিসরে সর্বাধিক সাবয়ারের যোগফল গণনা করতে ফাংশন Max_subarray(নোড, প্রথম, শেষ, আকার) কল করুন
-
উদাহরণ
#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
