আমাদের একটি পূর্ণসংখ্যা অ্যারে এবং একটি পূর্ণসংখ্যা ভেরিয়েবল অর্থাৎ 'X' দেওয়া আছে। কাজটি হল প্রথমে দেওয়া অ্যারে থেকে সাবঅ্যারে তৈরি করা এবং তারপর একটি সাবঅ্যারের সকল উপাদানকে একটি পূর্ণসংখ্যা X দিয়ে গুণ করা। শেষে সেই উপাদানগুলো খুঁজে বের করা যারা সর্বাধিক যোগফলে অবদান রাখবে।
বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -
ইন - int arr[] = {2, 4, 1, -5, -2}, X = 3
আউট - যেকোনো সাবঅ্যারের সব উপাদানকে X দিয়ে গুণ করে সাবঅ্যারে সম সর্বাধিক করা: 21
ব্যাখ্যা - আমাদের একটি অ্যারে এবং একটি পূর্ণসংখ্যা ভেরিয়েবল X দেওয়া আছে। প্রথমে দেওয়া অ্যারে থেকে সাবঅ্যারে বের করুন ধরুন, {2, 4, 1}। এখন একটি সাবঅ্যারের সকল উপাদানকে X অর্থাৎ 3 দিয়ে গুণ করুন তাই অ্যারেটি হবে {6, 12, 3, -5, -2}। শেষে, সর্বোচ্চ সাবঅ্যারে সম চেক করুন যা 6 + 12 + 3 = 21 দেবে।
ইন - int arr[] = {-1, 2, -6, 3, -4}, x = -1
আউট - যেকোনো সাবঅ্যারের সব উপাদানকে X দিয়ে গুণ করে সাবঅ্যারে সম সর্বাধিক করা: 11
ব্যাখ্যা - আমাদের একটি অ্যারে এবং একটি পূর্ণসংখ্যা ভেরিয়েবল X দেওয়া আছে। প্রথমে দেওয়া অ্যারে থেকে সাবঅ্যারে বের করুন ধরুন, {-1, -6, -4}। এখন একটি সাবঅ্যারের সকল উপাদানকে X অর্থাৎ -1 দিয়ে গুণ করুন তাই অ্যারেটি হবে {1, 2, 6, 3, 4}। শেষে, সর্বোচ্চ সাবঅ্যারে সম চেক করুন যা 1 + 6 + 4 = 11 দেবে।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি
- একটি পূর্ণসংখ্যা অ্যারে এবং একটি পূর্ণসংখ্যা ভেরিয়েবল 'X' ইনপুট নিন। অ্যারের আকার গণনা করুন এবং Max_Subarray(arr, size, x) ফাংশনে ডেটা পাস করুন।
- Max_Subarray(arr, size, x) ফাংশনের ভিতরে:
- arr_2[size][3] নামে একটি অ্যারে এবং temp নামে একটি টেম্পরারি ভেরিয়েবল ০ দিয়ে ডিক্লেয়ার করুন।
- memset() মেথড ব্যবহার করে 'arr_2' অ্যারের সকল উপাদানকে -1 দিয়ে ইনিশিয়ালাইজ করুন।
- i = ০ থেকে অ্যারের আকার পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে temp = max(temp, check(i, 0, arr, arr_2, size, x)) সেট করুন।
- temp রিটার্ন করুন।
- int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x) ফাংশনের ভিতরে:
- count = 0 নামে একটি টেম্পরারি ভেরিয়েবল ডিক্লেয়ার করুন।
- চেক করুন IF first == size তবে 0 রিটার্ন করুন।
- চেক করুন IF arr_2[first][last] != -1 তবে arr_2[first][last] রিটার্ন করুন।
- চেক করুন IF last == 0 তবে C++-এর ইনবিল্ট max ফাংশন কল করুন সর্বোচ্চ মান খুঁজে বের করতে: max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x)) এবং count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x)) সেট করুন।
- ELSE IF last == 1 চেক করুন তবে count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x)) এবং count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x)) সেট করুন।
- অন্যথায়, count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x)) সেট করুন।
- arr_2[first][last] = count রিটার্ন করুন।
- ফলাফল প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x){
int count = 0;
if(first == size){
return 0;
}
if(arr_2[first][last] != -1){
return arr_2[first][last];
}
if (last == 0){
count = max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x));
count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
}
else if(last == 1){
count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
}
else{
count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
}
return arr_2[first][last] = count;
}
int Max_Subarray(int arr[], int size, int x){
int arr_2[size][3];
int temp = 0;
memset(arr_2, -1, sizeof arr_2);
for(int i = 0; i < size; i++){
temp = max(temp, check(i, 0, arr, arr_2, size, x));
}
return temp;
}
int main(){
int arr[] = {2, 4, 1, -5, -2};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 3;
cout<<"Maximize the subarray sum after multiplying all elements of any subarray with X are: "<<Max_Subarray(arr, size, x);
return 0;
}
আউটপুট
উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি জেনারেট হবে
Maximize the subarray sum after multiplying all elements of any subarray with X are: 21
