C++-এ একটি দেওয়া রেঞ্জে সর্বোচ্চ সাবঅ্যারে সম (Maximum Subarray Sum)

আমাদের যেকোনো দেওয়া আকারের পূর্ণসংখ্যা উপাদান 지닌 একটি অ্যারে দেওয়া আছে। কাজটি হল দেওয়া অ্যারে থেকে সাবঅ্যারে তৈরি করে দেওয়া রেঞ্জের মধ্যে যেকোনো সম্ভাব্য ইনডেক্স মান থেকে শুরু করে সর্বোচ্চ যোগফল খুঁজে বের করা।

বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -

ইন - int arr[] = { 3, 2, -1, 6, 7, 2 }, int first = 0, int last = 5

আউট - একটি দেওয়া রেঞ্জে সর্বোচ্চ সাবঅ্যারে সম: 19

ব্যাখ্যা - আমাদের একটি অ্যারে দেওয়া আছে যাতে ধনাত্মক এবং ঋণাত্মক উভয় মান রয়েছে এবং একটি রেঞ্জ ০ থেকে ৫ পর্যন্ত অর্থাৎ অ্যারের সকল ইনডেক্স কভার করছে। তাই সর্বোচ্চ যোগফল যেকোনো সাবঅ্যারে থেকে হতে পারে 3 + 6 + 7 + 2 + 2 - 1 = 19।

ইন - int arr[] = {-2, 1, 3, 4, 8, 9, 23}, int first = 0, int last = 3

আউট - একটি দেওয়া রেঞ্জে সর্বোচ্চ সাবঅ্যারে সম: 8

ব্যাখ্যা - আমাদের একটি অ্যারে দেওয়া আছে যাতে ধনাত্মক এবং ঋণাত্মক উভয় মান রয়েছে এবং একটি রেঞ্জ ০ থেকে ৩ পর্যন্ত অর্থাৎ অ্যারের ০ থেকে ৩ ইনডেক্স কভার করছে। তাই সর্বোচ্চ যোগফল যেকোনো সাবঅ্যারে থেকে হতে পারে 1 + 3 + 4 = 8।

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি

• একটি ট্রি জন্য স্ট্রাকচার কনস্ট্রাক্ট করুন যা max_val, max_temp, total, sub_sum মেম্বার ভেরিয়েবল হিসেবে সংরক্ষণ করবে এবং ডিফল্ট কনস্ট্রাক্টর ব্যবহার করে max_val, max_temp, sum_sum এবং total কে সর্বোচ্চ মান দিয়ে সেট করুন।
• স্ট্রাকচারের একটি মেথড তৈরি করুন set_node নামে যা left.max_val, left.total + right.max_val এর মধ্যে সর্বোচ্চ হিসেবে max_val সেট করে, right.max_temp, right.total + left.max_temp-এর মধ্যে সর্বোচ্চ হিসেবে max_temp সেট করে, left.total + right.total হিসেবে total সেট করে এবং left.sub_sum, right.sub_sum, left.max_temp + right.max_val-এর মধ্যে সর্বোচ্চ হিসেবে sub_sum সেট করে তারপর node রিটার্ন করুন।
• build_tree নামে একটি মেথড তৈরি করুন যা ট্রি কনস্ট্রাক্ট করতে ব্যবহৃত হবে।
  • চেক করুন IF 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, মান ০, অ্যারের আকার -১, মান ১ আর্গুমেন্ট হিসেবে পাস করে।
• 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 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