इस समस्या में, हमें 0 से आरंभिक N तत्वों का एक सरणी arr[] दिया जाता है। हमारा कार्य C++ में m श्रेणी वृद्धि संचालन के बाद किसी सरणी में अधिकतम मान खोजने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण
ऐरे पर, हम प्रकार का m रेंज इंक्रीमेंट ऑपरेशन करेंगे,
अद्यतन [एल, आर, के] =श्रेणी के सभी तत्वों के लिए मूल्य के जोड़ें।
सरणी पर 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) की जटिलता बनाने वाली प्रत्येक क्वेरी के लिए सीमा पर पुनरावृति करता है।
प्रत्येक श्रेणी वृद्धि संचालन के लिए K को L में जोड़ना और 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