আমাদের একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে এবং কাজটি হল প্রথমে অ্যারের প্রিফিক্স বের করা এবং সেটি -1 দিয়ে গুণ করা, দ্বিতীয়ত প্রিফিক্স সম অ্যারে গণনা করা এবং শেষে জেনারেট করা প্রিফিক্স অ্যারেতে থেকে সর্বোচ্চ যোগফল বের করা।
প্রিফিক্স অ্যারে তৈরি হয় নিম্নরূপ:-
প্রিফিক্স অ্যারের প্রথম উপাদান prefixArray[0] = অ্যারের প্রথম উপাদান
প্রিফিক্স অ্যারের দ্বিতীয় উপাদান prefixArray[1] = prefixArray[0] + arr[1]
প্রিফিক্স অ্যারের তৃতীয় উপাদান prefixArray[2] = prefixArray[1] + arr[2]
প্রিফিক্স অ্যারের চতুর্থ উপাদান prefixArray[3] = prefixArray[2] + arr[3] ... ইত্যাদি।
বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -
ইন - 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+10 = 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+7+8+5 = 19 যা চূড়ান্ত আউটপুট।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি -
- একটি পূর্ণসংখ্যা অ্যারে এবং x = -1 নামে একটি টেম্পরারি ভেরিয়েবল ডিক্লেয়ার করুন তারপর arr[0] = arr[0] * x সেট করুন।
- অ্যারের আকার গণনা করুন। prefix_arry[size] নামে একটি প্রিফিক্স অ্যারে ডিক্লেয়ার করুন। create_prefix_arr(arr, size, prefix_array) ফাংশন কল করুন দেওয়া অ্যারে থেকে প্রিফিক্স অ্যারে জেনারেট করতে। প্রিফিক্স অ্যারে প্রিন্ট করুন।
- maximize_sum(prefix_array, size) ফাংশন কল করুন যেটি অ্যারের সর্বোচ্চ যোগফল সংরক্ষণ করবে।
- void create_prefix_arr(int arr[], int size, int prefix_array[]) ফাংশনের ভিতরে:
- prefix_array[0] = arr[0] সেট করুন।
- i = ০ থেকে অ্যারের আকার পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে prefix_array[i] = prefix_array[i-1] + arr[i] সেট করুন।
- int maximize_sum(int prefix_array[], int size) ফাংশনের ভিতরে:
- temp = -1 নামে একটি টেম্পরারি ভেরিয়েবল ডিক্লেয়ার করুন।
- i = ০ থেকে অ্যারের আকার পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে temp = max(temp, prefix_array[i]) সেট করুন।
- arr[temp + 1] নামে একটি অ্যারে ডিক্লেয়ার করুন এবং সকল উপাদান ০ দিয়ে ইনিশিয়ালাইজ করুন।
- i = ০ থেকে অ্যারের আকার পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে arr[prefix_array[i]]++ সেট করুন।
- max_sum = 0 নামে একটি টেম্পরারি ভেরিয়েবল ডিক্লেয়ার করুন। i = temp নামে একটি ভেরিয়েবল ডিক্লেয়ার করুন।
- WHILE i > 0 লুপ শুরু করুন। চেক করুন IF arr[i] > 0 তবে max_sum = max_sum + i এবং arr[i-1]-- এবং arr[i]-- ডিক্রিমেন্ট করুন। ELSE, i কে ১ কমানো।
- max_sum রিটার্ন করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
//প্রিফিক্স অ্যারে তৈরি
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];
}
}
//প্রিফিক্স অ্যারের সর্বোচ্চ যোগফল বের করা
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];
//প্রিফিক্স অ্যারে তৈরি করার জন্য ফাংশন কল
create_prefix_arr(arr, size, prefix_array);
//প্রিফিক্স অ্যারে প্রিন্ট
cout<<"Prefix array is: ";
for(int i = 0; i < size; i++) {
cout << prefix_array[i] << " ";
}
//প্রিফিক্স অ্যারের সর্বোচ্চ যোগফল প্রিন্ট
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
