আমাদের একটি পূর্ণসংখ্যা অ্যারে দেওয়া হয়েছে এবং কাজটি হল প্রথমে একটি অ্যারের উপসর্গ আনা এবং তারপরে এটিকে -1 দিয়ে গুণ করা, দ্বিতীয়ত একটি অ্যারের উপসর্গের যোগফল গণনা করা এবং সর্বশেষে তৈরি করা উপসর্গ অ্যারে থেকে সর্বাধিক যোগফল খুঁজে বের করা৷
প্রিফিক্স অ্যারে −
হিসাবে তৈরি হয়প্রিফিক্স অ্যারে[0] এর প্রথম উপাদান =একটি অ্যারের প্রথম উপাদান
prefixArray[1] এর দ্বিতীয় উপাদান =prefixArray[0] + arr[1]
prefixArray[2] এর তৃতীয় উপাদান =prefixArray[1] + arr[2]
prefixArray[3] এর চতুর্থ উপাদান =prefixArray[2] + arr[3]…..etc.
আসুন এর জন্য বিভিন্ন ইনপুট আউটপুট পরিস্থিতি দেখি -
এ − int arr[] ={2, 4, 1, 5, 2}
আউট − প্রিফিক্স অ্যারে হল:-2 2 3 8 10 অ্যারের উপসর্গকে -1 দিয়ে গুণ করে অ্যারের যোগফলকে সর্বাধিক করুন:21
ব্যাখ্যা - আমাদের একটি পূর্ণসংখ্যা অ্যারে দেওয়া হয়েছে। সুতরাং আমরা প্রথমে একটি অ্যারের প্রিফিক্স আনব যা 2 এবং এটি -1 এর সাথে একাধিক। সুতরাং, নতুন অ্যারে হবে {-2, 4, 1, 5, 2}। এখন, আমরা উপসর্গ অ্যারে গঠন করব যা হল {-2, 2, 3, 8, 10}। শেষ ধাপ হল -2+2+3+8+`0 =21 হিসাবে যোগফলকে সর্বাধিক করা যা চূড়ান্ত আউটপুট।
এ − int arr[] ={-1, 4, 2, 1, -9, 6};
আউট − উপসর্গ অ্যারে হল:1 5 7 8 -1 5 অ্যারের উপসর্গকে -1 দিয়ে গুণ করে অ্যারের যোগফলকে সর্বাধিক করুন:19
ব্যাখ্যা - আমাদের একটি পূর্ণসংখ্যা অ্যারে দেওয়া হয়েছে। সুতরাং আমরা প্রথমে একটি অ্যারের প্রিফিক্স আনব যা -1 এবং এটি -1 এর সাথে একাধিক। সুতরাং, নতুন অ্যারে হবে {1, 4, 2, 1, -9, 6}। এখন, আমরা প্রিফিক্স অ্যারে তৈরি করব যা হল {1, 5, 7, 8, -1, 5}। শেষ ধাপ হল যোগফলকে 1+5+8+5 =19 হিসাবে সর্বাধিক করা যা চূড়ান্ত আউটপুট।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি হল -
-
একটি পূর্ণসংখ্যা অ্যারে এবং একটি অস্থায়ী ভেরিয়েবলকে x থেকে -1 হিসাবে ঘোষণা করুন তারপর arr[0] to arr[0] * x সেট করুন।
-
একটি অ্যারের আকার গণনা. একটি উপসর্গ অ্যারেকে প্রিফিক্স_অ্যারি [সাইজ] হিসাবে ঘোষণা করুন। প্রদত্ত অ্যারে থেকে প্রিফিক্স অ্যারে তৈরি করতে একটি ফাংশন create_prefix_arr(arr, size, prefix_array) কল করুন। প্রিফিক্স অ্যারে প্রিন্ট করুন
-
maximize_sum(prefix_array, size) ফাংশনটিকে কল করুন যা অ্যারের সর্বাধিক যোগফল সংরক্ষণ করবে।
-
ফাংশনের ভিতর void create_prefix_arr(int arr[], int size, int prefix_array[])
-
প্রিফিক্স_অ্যারে[0]কে arr[0] এ সেট করুন।
-
একটি অ্যারের আকার পর্যন্ত i থেকে 0 পর্যন্ত লুপ শুরু করুন। লুপের ভিতরে, prefix_array[i] কে prefix_array[i-1] + arr[i] সেট করুন।
-
-
ফাংশনের ভিতরে int maximize_sum(int prefix_array[], int size)
-
একটি অস্থায়ী পরিবর্তনশীলকে temp হিসাবে ঘোষণা করুন এবং এটি -1 এ সেট করুন।
-
একটি অ্যারের আকার পর্যন্ত i থেকে 0 পর্যন্ত লুপ শুরু করুন। লুপের ভিতরে, temp max(temp, prefix_array[i])
হিসাবে সেট করুন -
একটি অ্যারেকে arr[temp +1] হিসাবে ঘোষণা করুন এবং একটি অ্যারের সমস্ত উপাদানকে 0 দিয়ে আরম্ভ করুন।
-
একটি অ্যারের আকার পর্যন্ত i থেকে 0 পর্যন্ত লুপ শুরু করুন। লুপের ভিতরে, arr[prefix_array[i]]++
সেট করুন -
একটি অস্থায়ী ভেরিয়েবলকে max_sum হিসাবে ঘোষণা করুন এবং এটি 0 এ সেট করুন। একটি পরিবর্তনশীলকে int i থেকে temp হিসাবে ঘোষণা করুন
-
i>0 থাকাকালীন লুপ শুরু করুন। IF arr[i]> 0 চেক করুন তারপর max_sum কে max_sum + i তে সেট করুন এবং arr[i-1]--- এবং arr[i]-- কমিয়ে দিন। অন্যথায়, i 1 দ্বারা হ্রাস করুন।
-
সর্বোচ্চ_সমষ্টি ফেরত দিন।
-
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
//create the prefix array
void create_prefix_arr(int arr[], int size, int prefix_array[]) {
prefix_array[0] = arr[0];
for(int i=0; i<size; i++) {
prefix_array[i] = prefix_array[i-1] + arr[i];
}
}
//find the maximum sum of prefix array
int maximize_sum(int prefix_array[], int size) {
int temp = -1;
for(int i = 0; i < size; i++) {
temp = max(temp, prefix_array[i]);
}
int arr[temp + 1];
memset(arr, 0, sizeof(arr));
for(int i = 0; i < size; i++) {
arr[prefix_array[i]]++;
}
int max_sum = 0;
int i = temp;
while(i>0) {
if(arr[i] > 0) {
max_sum = max_sum + i;
arr[i-1]--;
arr[i]--;
} else {
i--;
}
}
return max_sum;
}
int main() {
int arr[] = {2, 4, 1, 5, 2};
int x = -1;
arr[0] = arr[0] * x;
int size = sizeof(arr) / sizeof(arr[0]);
int prefix_array[size];
//call function to create a prefix array
create_prefix_arr(arr, size, prefix_array);
//print the prefix array
cout<<"Prefix array is: ";
for(int i = 0; i < size; i++) {
cout << prefix_array[i] << " ";
}
//print the maximum sum of prefix array
cout<<"\nMaximize the sum of array by multiplying prefix of array with -1 are:" <<maximize_sum(prefix_array, size);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে
Prefix array is: -2 2 3 8 10 Maximize the sum of array by multiplying prefix of array with -1 are: 21
