আমাদেরকে একটি পূর্ণসংখ্যা অ্যারে এবং একটি পূর্ণসংখ্যার পরিবর্তনশীল যেমন '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)
-
একটি অ্যারেকে int arr_2[size][3] হিসেবে ঘোষণা করুন এবং একটি অস্থায়ী পরিবর্তনশীলকে 0-এ temp হিসেবে ঘোষণা করুন।
-
C++ এ memset() পদ্ধতি ব্যবহার করে একটি অ্যারের ‘arr_2’-এর সমস্ত উপাদানকে -1 দিয়ে শুরু করে।
-
একটি অ্যারের আকার পর্যন্ত i থেকে 0 পর্যন্ত লুপ শুরু করুন। লুপের ভিতরে, ফাংশন max(temp, check(i, 0, arr, arr_2, size, x)) তে কল করার জন্য temp সেট করুন
-
রিটার্ন টেম্প।
-
-
ফাংশনের ভিতরে int চেক (int first, int last, int arr[], int arr_2[Max_size][3], int size, int x)
-
গণনা 0 হিসাবে একটি অস্থায়ী পরিবর্তনশীল ঘোষণা করুন.
-
প্রথমে IF =সাইজ চেক করুন তারপর 0
দিন -
IF arr_2[first][last] !=-1 চেক করুন তারপর arr_2[first][last] ফেরত দিন।
-
IF last =0 চেক করুন তারপর C++-এর ইনবিল্ট ম্যাক্স ফাংশনটিকে কল করুন ম্যাক্স(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x)) হিসাবে সর্বাধিক মান খুঁজে বের করতে এবং গণনা সেট করুন =সর্বোচ্চ(গণনা, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x))
-
অন্যথায় যদি শেষ =1 চেক করেন তাহলে গণনাকে max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x)) এ গণনা সেট করুন এবং গণনাকে max(count, arr[first] এ সেট করুন। + চেক (প্রথম + 1, 2, arr, arr_2, আকার, x))
-
অন্যথায়, গণনাকে সর্বোচ্চ(গণনা, arr[first] + check(first + 1, 2, arr, arr_2, size, x) এ সেট করুন);
-
গণনা করতে arr_2[প্রথম][শেষ] ফিরে আসুন।
-
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
#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
