এই সমস্যায়, আমাদেরকে 0 দিয়ে শুরু করা N উপাদানগুলির একটি অ্যারে অ্যারে [] দেওয়া হয়েছে। আমাদের কাজ হল C++ এ m রেঞ্জ ইনক্রিমেন্ট অপারেশনের পরে একটি অ্যারেতে সর্বাধিক মান খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
অ্যারেতে, আমরা টাইপের m রেঞ্জ ইনক্রিমেন্ট অপারেশন করব,
update[L, R, K] =রেঞ্জের সমস্ত উপাদানে K মান যোগ করুন।
অ্যারেতে m অপারেশন করার পর। আমাদের অ্যারেতে সর্বাধিক মান সহ উপাদানটি খুঁজে বের করতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
N = 6, m = 4
Update[][] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}} আউটপুট
34
ব্যাখ্যা
arr[] = {0, 0, 0, 0, 0, 0}
Update 1 {1, 4, 12} : arr[] = {0, 12, 12, 12, 12, 0}
Update 2 {0, 3, 5} : arr[] = {5, 17, 17, 17, 12, 0}
Update 3 {1, 5, 7} : arr[] = {5, 24, 24, 24, 19, 7}
Update 4 {3, 5, 10} : arr[] = {5, 24, 24, 34, 29, 17} সমাধান পদ্ধতি
সমস্যা সমাধানের একটি সহজ পদ্ধতি হল অ্যারের মানগুলিকে আপডেট করে এবং তারপরে সমস্ত অপারেশন সম্পন্ন করার পরে। অ্যারের সর্বাধিক উপাদান খুঁজুন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include<iostream>
using namespace std;
int findmax(int arr[], int N){
int maxVal = 0;
for(int i = 0; i < N; i++){
if(maxVal < arr[i]){
maxVal = arr[i];
}
}
return maxVal;
}
void updateVal(int arr[], int L, int R, int K){
for(int i = L; i <= R; i++ ){
arr[i] += K;
}
}
int main(){
int N = 5;
int arr[N] = {0};
int M = 4;
int rangeIncOperation[M][3] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}};
for(int i = 0; i < M; i++){
updateVal(arr, rangeIncOperation[i][0], rangeIncOperation[i][1], rangeIncOperation[i][2]);
}
cout<<"The maximum value in the array after "<<M<<" range increment operations is "<<findmax(arr, N);
return 0;
} আউটপুট
The maximum value in the array after 4 range increment operations is 34
এই ক্রিয়াকলাপটি ভাল তবে O(m*N) অর্ডারের জটিলতা তৈরি করে প্রতিটি প্রশ্নের জন্য সীমার উপরে পুনরাবৃত্তি করে।
একটি ভাল পদ্ধতি হল প্রতিটি পরিসীমা বৃদ্ধির অপারেশনের জন্য L-এ K যোগ করা এবং R+1 থেকে K বিয়োগ করা। এবং তারপরে সর্বশ্রেষ্ঠ সর্বোচ্চ মানটি সন্ধান করুন যেমন অ্যারের প্রতিটি মানের জন্য যোগফলের মান আপডেট করুন এবং অপারেশনে ঘটে যাওয়া সর্বাধিক মানটি সন্ধান করুন৷
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include<iostream>
using namespace std;
int FindMaximum(int a, int b){
if(a > b)
return a;
return b;
}
int findmax(int arr[], int N){
int maxVal = 0;
int sum = 0;
for(int i = 0; i < N; i++){
sum += arr[i];
maxVal = FindMaximum(maxVal, sum);
}
return maxVal;
}
void updateVal(int arr[], int L, int R, int K){
arr[L] += K;
arr[R+1] -= K;
}
int main(){
int N = 5;
int arr[N] = {0};
int M = 4;
int rangeIncOperation[M][3] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}};
for(int i = 0; i < M; i++){
updateVal(arr, rangeIncOperation[i][0], rangeIncOperation[i][1], rangeIncOperation[i][2]);
}
cout<<"The maximum value in the array after "<<M<<" range increment operations is "<<findmax(arr, N);
return 0;
} আউটপুট
The maximum value in the array after 4 range increment operations is 34
